检查字符串是否包含所有唯一字符

Question

// O(N) - 没有额外的数据结构...

private boolean isUniqueWithoutDS(String str){

    boolean value = true;

    int checker = 0;

    for (int i = 0; i < str.length(); i++) {

        int c = str.charAt(i) - 'a';

        System.out.println("checker is : " + checker);

        System.out.println("1<<c is " + (1<<c));   

        if((checker & (1 << c))>0){

            value = false;

            break;

        }

        checker = checker | 1<<c;

    }

    return value;

}

这是我的代码并且工作正常，我无法理解它如何处理大写字母和小写字母组合的字符串。例如“ Zizu”有效。对于所有小写字母字符串，它都有效，我也知道它是如何工作的。

Answer 1

好吧，答案可能取决于语言，但在 Java 中（JLS 15.19。移位运算符）：如果左侧操作数的提升类型为int，则仅将右侧操作数的最低五位用作移位距离。就好像右边的操作数是按位逻辑 AND 运算符&（§15.22.1）和掩码值0x1f( 0b11111)。因此，实际使用的移动距离总是在0到 的范围内31，包括在内。所以就像你执行c = c & 0x1f, or一样c = c % 32，为了运算符的目的，大写A和小写都a变成了 ,c的值。0<<对于 32 位类型，我假设其他语言可能也有类似的工作方式int。

Answer 2

另一种检查字符串是否包含所有唯一字符的方法——在O(N)中：使用无限循环使用双变量 i (i=0) 和 j=(n-1 [其中 n-是字符串长度])检查每个第 i 个字符是否等于第 j 个字符3.1 if [i-th char == j-th && i != j char], break loop cause string contain duplicate chars.&nbsp;（i != j 表示比较相同的字符）3.2 减少 j 并设置 j 为 n-1 和 i += 1，当 j = 0 [这部分很棘手]重复第 3 步，除非 i 变成第 n-1 个大小代码&nbsp; String s = "abcde";&nbsp; &nbsp; int i = 0;&nbsp; &nbsp; int j = s.length()-1;&nbsp; &nbsp; boolean flag = true;&nbsp; &nbsp; while(true) {&nbsp; &nbsp; &nbsp; &nbsp; if(i == s.length()-1)&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; break;&nbsp; &nbsp; &nbsp; &nbsp; // DUPLICATE FOUND&nbsp; &nbsp; &nbsp; &nbsp; if(i != j && s.charAt(i) == s.charAt(j)) {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; flag = false;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; break;&nbsp; &nbsp; &nbsp; &nbsp; }else {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; j--;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; // COMPARING DONE AGAINST i-TH CHAR TO ALL OTHER CHARS, INCREMENT i NOW&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; if(j == 0) {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; j = s.length()-1;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; i += 1;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;&nbsp; &nbsp; }&nbsp; &nbsp; if(flag)&nbsp; &nbsp; &nbsp; &nbsp; System.out.println("unique");&nbsp; &nbsp; else&nbsp; &nbsp; &nbsp; &nbsp; System.out.println("non-unique");

Answer 3

我建议使用大小为 256 的数组来存储每个字符的计数（假设有 256 个可能的字符），在循环开始时将其设置为值 0。然后，当您获取每个下一个字符时，只需简单地增加每个位置。最后，有一个快速 hack 检查位置中的值是 0 还是 1（例如，freq[i] == !!freq[i])这个 if 语句[freq[i] == !!freq[i]]应该适用于数组中的所有 256 个项目。更新：unsigned int isDistinctStr(char *str);unsigned int isDistinctStr(char *str) {&nbsp; &nbsp; unsigned int ct, freq[256], i, j;&nbsp; &nbsp; char ch;&nbsp; &nbsp; for (i = 0; i < 256; i++) {freq[i] = 0;}&nbsp; &nbsp; for (ct = 0; ch = *str; str++) {&nbsp; &nbsp; &nbsp; &nbsp; j = (unsigned int) (ch & 0xffu);&nbsp; &nbsp; &nbsp; &nbsp; freq[j]++;&nbsp; &nbsp; }&nbsp; &nbsp; for (j = 0; j < 256; j++) {&nbsp; &nbsp; &nbsp; &nbsp; if (freq[j] == !!freq[j]) {ct++;}&nbsp; &nbsp; }&nbsp; &nbsp; return (ct == 256) ? 1 : 0;}