从两个字符串中删除重复的字符。

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

- adam.kubi

---

你认为这个可以快多少？你需要至少对每个字符串进行一次遍历，而且你的 bitSet 操作应该是 O(1)。 - Scott Hunter

在我看来，我认为我设计了一个不错的解决方案，但是我觉得可能有一些我不知道的技巧，所以想在这里问一下 @ScottHunter。 - adam.kubi

您IP地址为143.198.54.68，由于运营成本限制，当前对于免费用户的使用频率限制为每个IP每72小时10次对话，如需解除限制，请点击左下角设置图标按钮（手机用户先点击左上角菜单按钮）。 - AJMansfield

@AJMansfield 谢谢，我在粘贴代码之前忘记删除它了。我正在使用少量数据在本地测试它。 - adam.kubi

只是为了确保我理解你在做什么，你是要从s2中过滤掉所有出现在s1中的字符，对吗？ - AJMansfield

Answer 1

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

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

如果你改为使用稀疏查找表，例如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之外的字符。

- AJMansfield