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

Question

我试图比较两个字符串并识别重复的单词。例如

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

比较String1和String2将返回单词；“名字”。

我知道有可能将这两个字符串拆分成一个单词数组，然后在二维数组中迭代每个字符串的每个单词。然而，在O（n^2）时，这在计算上是昂贵的，我想知道是否有更快的方法？

谢谢。

编辑：为了清晰起见更改了示例。

Answer 1

一个简单的解决方案是使用集合。交叉点番石榴的方法集。这很简单：

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]

您还可以在此线程上找到有关检测集合相交的算法的更多信息。

Answer 2

在获得字数组的字符串后：

可以将第一个数组中的所有元素添加到hashmap中，然后扫描第二个数组，查看hashmap中是否存在每个元素。由于对hashmap的访问时间是O（1），这将是O（n m）时间复杂度。

如果不想使用额外的空间，可以对两个数组进行O（nlogn）排序，然后比较O（NM）中的项目，这样就得到了O（nlogn）总数。