确定一个字符串有没有使用额外的数据结构，并没有小写字符假设所有的独特字符 [英] Determining a string has all unique characters without using additional data structures and without the lowercase characters assumption
问题描述
这是在的破解编码面试的书的问题之一由盖尔Laakmann麦克道尔：
This is one of the questions in the Cracking the Coding Interview book by Gayle Laakmann McDowell:
实现的算法来确定一个字符串有所有不同的字符。如果你不能使用哪些额外的数据结构？
Implement an algorithm to determine if a string has all unique characters. What if you can not use additional data structures?
的作者写道：
我们可以用一个位向量，减少我们的空间使用一点点。我们假定，在低于code，该字符串只有小写'A'到Z。这将允许我们使用只是一个单一的int。
We can reduce our space usage a little bit by using a bit vector. We will assume, in the below code, that the string is only lower case
'a'through'z'. This will allow us to use just a single 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。相反，该字符串可以包含任何类型的字符和mdash的;像ASCII字符或统一code字
Let's say we get rid of the assumption that "the string is only lower case 'a' through 'z'". Instead, the string can contain any kind of character—like ASCII characters or Unicode characters.
有没有解决方案，高效为作者（或接近是同样有效的解决方案作者的）？
Is there a solution as efficient as the author's (or a solution that comes close to being as efficient as the author's)?
相关问题：
- <一个href="http://stackoverflow.com/questions/19484406/detecting-if-a-string-has-unique-characters-comparing-my-solution-to-cracking">Detecting如果一个字符串具有独特的特征：比较我的解决方案，以＆QUOT;破解编码面试＆QUOT;
- <一个href="http://stackoverflow.com/questions/9141830/explain-the-use-of-a-bit-vector-for-determining-if-all-characters-are-unique">Explain使用位向量的确定是否所有的字符都是唯一
- 字符串独特的字符
- <一个href="http://stackoverflow.com/questions/17357370/implementing-an-algorithm-to-determine-if-a-string-has-all-unique-characters">Implementing一种算法来确定一个字符串有所有不同字符
- <一个href="http://stackoverflow.com/questions/4987863/determine-if-a-string-has-all-unique-characters">determine如果一个字符串具有所有独特的角色？
- Detecting if a string has unique characters: comparing my solution to "Cracking the Coding Interview?"
- Explain the use of a bit vector for determining if all characters are unique
- String unique characters
- Implementing an algorithm to determine if a string has all unique characters
- determine if a string has all unique characters?
推荐答案
对于asccii字符集，你可以重新present的256位在4多头：C数组你基本上手$ C $
for the asccii character set you can represent the 256bits in 4 longs: you basically hand code an array.
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;
}
您可以使用下面的code，产生了类似的方法UNI code人物的身体：
You can use the following code to generate the body of a similar method for unicode characters:
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);
}
这篇关于确定一个字符串有没有使用额外的数据结构，并没有小写字符假设所有的独特字符的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
