java - 从 2 个字符串中删除重复字符

Question

我需要从字符串中删除重复的字符。我用这样的 BitSet 实现了它

private static String removeDup(String s1, String s2) {
    BitSet bitSet = new BitSet(26);
    char[] s1Chars = s1.toCharArray();

    for (char s1Char : s1Chars) {
        bitSet.set(s1Char);
    }

    char[] s2Chars = s2.toCharArray();
    StringBuilder sb = new StringBuilder();
    for (char s2Char : s2Chars) {
        if (bitSet.get(s2Char)) {
            //System.out.println("Duplicate " + s2Char);
        } else {
            sb.append(s2Char);
        }
    }

    return sb.toString();
}

虽然这种方法有效，但在时间和空间复杂度方面是否有更好的优化方法？谢谢

例如

• 输入:"hello", "world"
• 输出:wrd

Answer 1

您的实现存在一个问题，即它需要的存储位数等于字符串中的最高字符值，并且仅适用于 BMP 字符。请注意字符 a实际上对应于 97 的 char 值。你在哪里分配 BitSet ，你给它传递了一个 26 的大小参数，但这是没有意义的；然而，值为 256 可能会给您带来一些小的性能提升。

如果您要在包含 CJK 表意文字的字符串上使用它，您可能会使用多达 8 kiB 的存储空间 BitSet .

如果您改为使用稀疏查找表，例如 Set<Character> ，您可以显着降低存储需求，但这会将运行时间从 O(n) 增加到 O(n log n)。

另一个可能的改进是并行化算法。然而，添加并行化只会使其对于非常大的字符串更快，而对于更小的字符串可能会显着变慢。在 java-8 , 可以这样做:

private static String removeDup(String s1, String s2) {
    Set<Integer> points = s1.codePoints().collect(Collectors.toSet());
    return s2.codePoints().parallel().filter(c->!points.contains(c))
        .collect(StringBuilder::new, StringBuilder::appendCodePoint,
            StringBuilder::append).toString();
}

这还具有适用于 BMP 之外的字符的优势。