0

これはここからの質問です

レーベンシュタイン距離が1の場合、2つの単語は友達です（詳細については、http：//en.wikipedia.org/wiki/Levenshtein_distanceを参照してください）。つまり、単語Xの1文字だけを追加、削除、または置換して、単語Yを作成できます。単語のソーシャルネットワークは、すべての友達、すべての友達、すべての友達の友達などで構成されます。 。この単語リストを使用して、「hello」という単語のソーシャルネットワークの大きさを示すプログラムを作成しますhttps://raw.github.com/codeeval/Levenshtein-Distance-Challenge/master/input_levenshtein_distance.txt 入力

プログラムは、最初の引数としてファイル名へのパスを受け入れる必要があります。入力ファイルには単語リストが含まれています。このリストは、https：//raw.github.com/codeeval/Levenshtein-Distance-Challenge/master/input_levenshtein_distance.txtからも入手できます。 出力

「こんにちは」という単語のソーシャルネットワークの大きさを印刷します。たとえば、「abcde」という単語のソーシャルネットワークは4846です。

誰かが同じためのいくつかのロジックを思い付くのを助けることができますか？在宅勤務の問題ではありません。

4

3 に答える 3

5

簡単な解決策は、問題をグラフ: 、 where 、としてO(n^2)モデル化することです。
G = (V,E)V = { all words }E = { (u,v) | u is friend of v }

これから、次のアルゴリズムが続きます (高レベルの疑似コード)。

1. Create the graph from the data
2. Run a BFS from the source, and continue while there are more 
   vertices that can be discovered. 
3. When you are done, the size of the `visited` set is the size of 
   the social network (this set is the actual social network)

複雑：

  • このグラフの作成はO(n^2)(すべてのペアをチェック) です。
  • BFSもO(n^2)以来アルゴリズム|E| < n^2の合計を取得しO(n^2)
于 2012-05-25T11:31:03.753 に答える
2

レーベンシュタイン距離を見つける方法を知っている場合、知っておく必要があるのは、単語のペア間のレーベンシュタイン距離だけです。

ここでは、完全なグラフを描く必要はありません。より良いアプローチは、単語のソーシャル ネットワークに存在することがわかっている単語のハッシュ テーブルを維持することです。このようにして、冗長なペアを回避できます。これがまさに私が意味することです。

単語を次のように仮定します。 Right Bright Wright

すべてのペアの編集距離は 1 です。しかし、Right のソーシャル ネットワークだけが必要な場合は、Bright と Wright のペアを考慮する必要はありません。

チェックリストに追加がなくなるまで、チェックされたすべての単語についてこの方法を続けます。

于 2012-05-25T14:13:21.027 に答える
2

BFS や DFS、またはグラフのツリー カバーを返す任意のアルゴリズムを使用できます。好みに合わせて調整できます。

于 2012-05-25T13:22:39.477 に答える