确定字符串具有所有唯一字符，而不使用其他数据结构且不使用小写字符假设

这是Gayle Laakmann McDowell在“ Cracking the Coding Interview”一书中的一个问题：

实现算法以确定字符串是否具有所有唯一字符。 如果您不能使用其他数据结构怎么办？

作者写道：

我们可以通过使用位向量来减少空间使用量。 我们将在下面的代码中假设字符串只是小写'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 < 0) return false; checker |= (1 << val); } return true; } 

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

有没有像作者那样高效的解决方案（或者一种与作者一样高效的解决方案）？

相关问题：

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

Answer 1

对于asccii字符集，您可以表示4个long中的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; } 

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

 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

我认为我们需要对“附加数据结构”进行一般性和实用的定义。 直觉上，我们不希望将每个标量整数或指针称为“数据结构”，因为这使得对“附加数据结构”的禁止无效。

我建议我们从big-O表示法中借用一个概念：“附加数据结构”是随着数据集的大小而增长的结构。

在当前情况下，OP引用的代码似乎具有O（1）的空间要求，因为位向量恰好适合整数类型。 但正如OP所暗示的那样，问题的一般forms实际上是O（N）。

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

Answer 4

以下算法怎么样？

脚步：

将字符串转换为小写。

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

设置变量数据= 0

计算字符串-97中第一个字符的offset = ascii值

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

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

否则，如果我们还没有看到字符重复，则通过执行data = data |按位OR来设置该字符的位 面具

继续直到角色结束。