比較2個字符串以查找它們是否包含與java相同的單詞

Question

我正在使用Levenshtein距離，它是一個字符串度量，用於測量兩個序列之間的差異量以找出兩個字符串之間的差異百分比。我想使用更好的方法來聲明字符串與字符串中的單詞相似。

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

我知道我可以比較每個字符串的第一個單詞，然後是第二個等，但如果像我提出的最後一個例子發生的情況下，這將不會有效。

我在想也許比較第一個字符串中的第一個單詞和第二個字符串中的所有單詞，但恐怕這會讓這個過程變得很慢。

Answer 1

比較第一個字符串中的每個單詞與第二個字符串中的所有單詞可能會產生比Levenshtein距離稍好的性能，但是會在相同的數量級上。 Levenstein距離爲O（m * n），算法爲O（m^2）（其中m和n是字符串的長度）。

如果你只關心匹配話（例如，「顏色」和「顏色」將被視爲兩個完全不同的字符串）和無視詞序（例如，「紅色」和「紅色」會被視爲兩個相同的字符串），並且您不關心算法的空間複雜性，可以創建第一個字符串的單詞索引（例如哈希表），然後將第二個字符串中的每個單詞與該索引進行比較。如果您的索引使用的是具有恆定時間插入和刪除的數據結構，則會產生複雜度爲O（m + n）的算法。