java - java中空间和时间复杂度较低的panagram

Question

我已经在 O(n) 时间和空间复杂度下实现了 panagram 程序。我希望我的程序具有 O(n) 时间复杂度和 O(1) 空间复杂度。

我的步骤是:

1. 将我的字符串转换为字符数组。
2. 将所有字符添加到树集中(避免重复)
3. 如果树集的大小为 26，我将打印为 panagram。

是否有任何优化方法可以将我的空间复杂度降低到 O(1)？

Answer 1

据我所知，你想检查你的字符串是否是字母组合。

如果您避免从字符串创建字符数组并从原始字符串迭代字符，您的复杂度将是 O(N*logA) 时间和 O(A) 空间，其中 A - 字母表大小。在您的情况下，A 是常数，因此只有在避免从字符串创建字符数组的情况下重写程序时，您才会拥有 O(N) 时间和 O(1) 空间。

附言不要使用树来存储字符，最好使用大小为 A 的数组来存储字符在字符串中出现的次数。即使您可以使用大小为 A 或字节数为 A/8 的位数组来存储特定字符是否出现在字符串中。并且此实现中的时间复杂度将是 O(N) 而不是 O(N*logA)，但这在复杂度估计中并不重要，因为 A 是常数，但即使如此，普通数组实现也会更快(可能是几个倍)比在树中存储字符的存在。