热门文章
 当前位置：技术文章 > 编程面试题 >

确定字符串具有所有唯一字符，无需使用其他数据结构，也无需假设使用小写字符

问题内容：

这是Gayle Laakmann McDowell 撰写的《 破解编码面试
》
中的问题之一：

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

作者写道：

我们可以通过使用位向量来稍微减少空间使用量。我们假设，在下面的代码，该字符串只有较低的情况下'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字符。

有没有像作者一样有效的解决方案（或者几乎和作者一样高效的解决方案）？


问题答案：

对于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);
}