比较2个字符串以查找它们是否包含与java相同的单词

Question

我正在使用Levenshtein距离，它是一个字符串度量，用于测量两个序列之间的差异量以找出两个字符串之间的差异百分比。我想使用更好的方法来声明字符串与字符串中的单词相似。

例如：可以说我有一个2段的字符串，第二个字符串只包含第一个字符串的第二段。

我知道我可以比较每个字符串的第一个单词，然后是第二个等，但如果像我提出的最后一个例子发生的情况下，这将不会有效。

我在想也许比较第一个字符串中的第一个单词和第二个字符串中的所有单词，但恐怕这会让这个过程变得很慢。

Answer 1

比较第一个字符串中的每个单词与第二个字符串中的所有单词可能会产生比Levenshtein距离稍好的性能，但是会在相同的数量级上。 Levenstein距离为O（m * n），算法为O（m^2）（其中m和n是字符串的长度）。

如果你只关心匹配话（例如，“颜色”和“颜色”将被视为两个完全不同的字符串）和无视词序（例如，“红色”和“红色”会被视为两个相同的字符串），并且您不关心算法的空间复杂性，可以创建第一个字符串的单词索引（例如哈希表），然后将第二个字符串中的每个单词与该索引进行比较。如果您的索引使用的是具有恒定时间插入和删除的数据结构，则会产生复杂度为O（m + n）的算法。