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

Question

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

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

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

我知道可以将这两个字符串拆分为一个单词数组，然后遍历二维数组中每个字符串的每个单词。然而，这在 O(n^2) 时计算成本很高，我想知道是否有更快的方法来做到这一点？

谢谢。

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

Answer 1

将字符串转换为单词数组后：

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

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

Answer 2

一种简单的解决方案是使用Sets.intersectionGuava 的方法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 交集的算法的更多信息。