7

2 つの文字列を比較して、重複する単語を識別できるようにしようとしています。例えば;

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

String1 と String2 を比較すると単語が返されます。"名前"。

これら 2 つの文字列を単語の配列に分割し、2 次元配列の各文字列の各単語を反復処理できることはわかっています。ただし、これは O(n^2) で計算コストが高く、これを行うより高速な方法があるかどうか疑問に思っていましたか?

ありがとう。

編集: わかりやすくするために例を変更しました。

4

2 に答える 2

13

文字列を単語配列に取得した後:

最初の配列のすべての要素をハッシュマップに追加してから、2 番目の配列をスキャンして、各要素がハッシュマップに存在するかどうかを確認できます。ハッシュマップへのアクセス時間は O(1) であるため、これは O(n+m) 時間の複雑さになります。

余分なスペースを使用したくない場合は、両方の配列を O(nlogn) で並べ替えてから、O(n+m) の項目を比較すると、合計で O(nlogn) になります。

于 2013-01-08T16:10:42.230 に答える
6

簡単な解決策の 1 つはSets.intersection、Guava の の方法を使用すること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 の交差を検出するアルゴリズムの詳細については、このスレッドを参照してください。

于 2013-01-08T16:16:25.217 に答える