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

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)中：

1. 使用无限循环

2. 使用双变量 i (i=0) 和 j=(n-1 [其中 n-是字符串长度])

3. 检查每个第 i 个字符是否等于第 j 个字符

   3.1 if [i-th char == j-th && i != j char], break loop cause string contain duplicate chars. （i != j 表示比较相同的字符）

   3.2 减少 j 并设置 j 为 n-1 和 i += 1，当 j = 0 [这部分很棘手]

4. 重复第 3 步，除非 i 变成第 n-1 个大小

代码

  String s = "abcde";

    int i = 0;

    int j = s.length()-1;

    boolean flag = true;

    while(true) {

        if(i == s.length()-1)

            break;

        // DUPLICATE FOUND

        if(i != j && s.charAt(i) == s.charAt(j)) {

            flag = false;

            break;

        }else {

            j--;

            // COMPARING DONE AGAINST i-TH CHAR TO ALL OTHER CHARS, INCREMENT i NOW

            if(j == 0) {

                j = s.length()-1;

                i += 1;

            }

        }           

    }

    if(flag)

        System.out.println("unique");

    else

        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) {

    unsigned int ct, freq[256], i, j;

    char ch;

    for (i = 0; i < 256; i++) {freq[i] = 0;}

    for (ct = 0; ch = *str; str++) {

        j = (unsigned int) (ch & 0xffu);

        freq[j]++;

    }

    for (j = 0; j < 256; j++) {

        if (freq[j] == !!freq[j]) {ct++;}

    }

    return (ct == 256) ? 1 : 0;

}