1

私は、レーベンシュタイン距離を介して関連する単語の「ソーシャルネットワーク」を見つけることを含むコードチャレンジをオンラインで行っています。私のレーベンシュタイン関数は正しいです。グローバルセットに再帰的に追加し、タプルのマップをブール値に使用して、単語のペアのレーベンシュタイン距離が1であるかどうかをキャッシュします。コードは5秒で終了することになっています。 これがどのように可能に近いのかわかりません。これを可能にするいくつかのaha洞察があると確信しています。誰もがすぐにそれを見ることができますか？

問題の説明： レーベンシュタイン距離が1の場合、2つの単語は友達です。つまり、単語Xの1文字を追加、削除、または置換して、単語Yを作成できます。単語のソーシャルネットワークは、すべての友達とその友達で構成されます。すべての友達、すべての友達の友達など。この単語リストを使用して、「こんにちは」という単語のソーシャルネットワークの大きさを教えてくれるプログラムを作成します

私の擬似コード：

get_network(friend)
  if friend not in network
    add friend to network
    friends = []
    check friend against all words in network
      consult cache or calculate lev distance
      cache if necessary, append to friends if necessary
    for all friends
      get_network(friend)

質問を言い換えると、「効率の天文学的な向上を可能にする基本的な洞察は何ですか？」

4

0 に答える 0