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

Question

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

我的步骤是：

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

有没有优化的方法将我的空间复杂度降低到O(1)？

Answer 1

据我所知，你想检查一下，如果你的字符串是潘格拉姆。

如果您避免从字符串创建字符数组，而从原始字符串迭代字符，您的复杂性将是O(N*洛嘎)时间和O(A)空间，其中A字母表大小。在您的示例中，A是常量，所以只有在重写程序时才有O(N)时间和O(1)空间，这样才能避免从字符串中创建字符数组。

不要使用树来存储字符，最好使用A大小的数组来存储字符串中出现多少次字符。甚至您也可以使用A大小的位数组或字节计数的A/8来存储特定字符是否以字符串表示。这种实现的时间复杂度将是O(N)而不是O(N*洛嘎)，但在复杂度估计方面并不重要，因为A是常数，但即使是这样，普通数组实现也比在树中存储字符的速度快(可能快几倍)。

Answer 2

在这里，我对程序进行了修改，以便使用位向量从图书Cracking the coding interview中找到字符串程序中的重复字符。

时间复杂度O(n)空间复杂度O(1)

    String str = "abcdefghijklmnopqrstuvwxyz";
    int checker = 0;
    for (int i = 0; i < str.length(); i++) {
        int val = str.charAt(i) - 'a';
        checker |= (1 << val);
    }
    if (checker == 67108863)// 67108863 == 0b11111111111111111111111111
        System.out.println("Panagram");
    else
        System.out.println("Not Panagram");

Answer 3

你可以用一点来表示一个字符。

'a' -> 2^0 = 1
'b' -> 2^1 = 2
'c' -> 2^3 = 4
....
'z' -> 2^25

然后用26位来表示26个字符。

static int ALL = (1 << 26) - 1;

public static boolean isPanagram(String s) {
    int aggregate = 0;
    for (int i = 0, size = s.length(); i < size; ++i) {
        char c = Character.toLowerCase(s.charAt(i));
        if (c >= 'a' && c <= 'z')
            aggregate |= 1 << (c - 'a');
    }
    return aggregate == ALL;
}