比较java中的两个字符串并识别重复的单词

Question

我正在尝试比较两个字符串并识别重复的单词.例如;

String1 = "Hello, my name is John."
String2 = "Can you tell me your name please?"

比较String1和String2将返回单词; "名称".

我知道可以将这两个字符串拆分成一个单词数组,然后迭代二维数组中每个字符串的每个字.然而,这在O(n ^ 2)计算上是昂贵的,我想知道是否有更快的方法这样做？

谢谢.

编辑:为了清晰起见,更改了示例.

Answer 1

获取字符串数组后:

您可以将第一个数组中的所有元素添加到散列映射中,然后扫描第二个数组以查看散列映射中是否存在每个元素.由于对散列映射的访问时间是O(1),因此这将是O(n + m)时间复杂度.

如果您不想使用额外的空间,可以在O(nlogn)中对两个数组进行排序,然后比较O(n + m)中的项目,这些项目总共会得到O(nlogn).

Answer 2

一个简单的解决方案是使用Sets.intersection番石榴的方法Sets.这很简单:

String s1 = "Hello, my name is John.";
String s2 = "Can you tell me your name?";
Splitter splitter = Splitter.onPattern("\\W").trimResults().omitEmptyStrings();
Set<String> intersection = Sets.intersection(//
        Sets.newHashSet(splitter.split(s1)), //
        Sets.newHashSet(splitter.split(s2)));
System.out.println(intersection);

输出:

[name]

您还可以找到有关算法的更多信息,以检测此线程上的Set intersection .