确定字符串具有所有唯一字符，无需使用额外的数据结构且无需小写字符假设

Question

这是问题中的问题之一 破解编码面试 书 作者：盖尔·拉克曼·麦克道威尔：

实现一个算法来确定字符串是否包含所有唯一字符。如果不能使用额外的数据结构怎么办？

作者写道：

我们可以通过使用位向量来减少一点空间使用。在下面的代码中，我们假设字符串只是小写 'a' 通过 'z'. 。这将允许我们只使用一个 int。

作者有这样的实现：

public static boolean isUniqueChars(String str) {
    int checker = 0;
    for (int i = 0; i < str.length(); ++i) {
        int val = str.charAt(i) - 'a';
        if ((checker & (1 << val)) > 0)
            return false;
        checker |= (1 << val);
    }
    return true;
}

假设我们摆脱了“字符串只是小写”的假设 'a' 通过 'z'”。相反，该字符串可以包含任何类型的字符，例如 ASCII 字符或 Unicode 字符。

是否有一个解决方案与作者的解决方案一样有效（或者一个接近于作者的解决方案）？

相关问题：

• 检测字符串是否具有唯一字符：将我的解决方案与“破解编码面试？”进行比较
• 解释如何使用位向量来确定所有字符是否唯一
• 字符串唯一字符
• 实现一种算法来确定字符串是否具有所有唯一字符
• 确定字符串是否包含所有唯一字符？

Answer 1

对于 asccii 字符集，您可以用 4 个长整型表示 256 位：您基本上手动编写了一个数组。

public static boolean isUniqueChars(String str) {
    long checker1 = 0;
    long checker2 = 0;
    long checker3 = 0;
    long checker4 = 0;
    for (int i = 0; i < str.length(); ++i) {
        int val = str.charAt(i);
        int toCheck = val / 64;
        val %= 64;
        switch (toCheck) {
            case 0:
                if ((checker1 & (1L << val)) > 0) {
                    return false;
                }
                checker1 |= (1L << val);
                break;
            case 1:
                if ((checker2 & (1L << val)) > 0) {
                    return false;
                }
                checker2 |= (1L << val);
                break;
            case 2:
                if ((checker3 & (1L << val)) > 0) {
                    return false;
                }
                checker3 |= (1L << val);
                break;
            case 3:
                if ((checker4 & (1L << val)) > 0) {
                    return false;
                }
                checker4 |= (1L << val);
                break;
        }            
    }
    return true;
}

您可以使用以下代码为 un​​icode 字符生成类似方法的主体：

static void generate() {
    StringBuilder sb = new StringBuilder();
    for (int i = 0; i < 1024; i++) {
        sb.append(String.format("long checker%d = 0;%n", i));
    }
    sb.append("for (int i = 0; i < str.length(); ++i) {\n"
            + "int val = str.charAt(i);\n"
            + "int toCheck = val / 64;\n"
            + "val %= 64;\n"
            + "switch (toCheck) {\n");
    for (int i = 0; i < 1024; i++) {
        sb.append(String.format("case %d:\n"
                + "if ((checker%d & (1L << val)) > 0) {\n"
                + "return false;\n"
                + "}\n"
                + "checker%d |= (1L << val);\n"
                + "break;\n", i, i, i));
    }
    sb.append("}\n"
            + "}\n"
            + "return true;");
    System.out.println(sb);
}

Answer 2

你只需要一根线...实际上不到一行：

if (str.matches("((.)(?!.*\\1))*"))

这使用负前瞻来断言每个字符在字符串中后面不会重复。

这种方法的时间复杂度为 O(n^2)，因为对于输入中的所有 n 个字符，将比较后面的所有字符（其中有 n 个）是否相等。

Answer 3

我认为我们需要对“附加数据结构”有一个通用且实用的定义。直观上，我们不想将每个标量整数或指针称为“数据结构”，因为这使得任何“附加数据结构”的禁止变得毫无意义。

我建议我们借用大O符号中的一个概念：“附加数据结构”是一种随着数据集大小而增长的数据结构。

在本例中，OP 引用的代码似乎具有 O(1) 的空间要求，因为位向量恰好适合整数类型。但正如 OP 所暗示的，问题的一般形式实际上是 O(N)。

一般情况的解决方案的一个示例是使用两个指针和一个嵌套循环来简单地比较每个字符。空间要求是 O(1)，但时间要求是 O(N^2)。

Answer 4

下面的算法怎么样？

脚步：

将字符串转换为小写。

循环遍历字符串中的每个字符

设置变量数据 = 0

计算偏移量 = 字符串中第一个字符的 ascii 值 - 97

使用 mask = 1 << offset 设置该位置的标志

如果按位 AND 返回 true，则说明字符重复（掩码和数据），因此请在此处中断。

否则，如果我们尚未看到字符重复，请通过做一个位或进行数据=数据|来为该角色设置位。面具

继续直到字符结束。