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

Question

这是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 << 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;
}

您可以使用以下代码为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);
}