ruby - 2 つの単語の間に隣接する単語のリストを見つける

Question

私は練習のためにプログラミングの課題に取り組んでおり、解決策を実装するために使用する適切なデータ構造/アルゴリズムを見つけるのに苦労しています.

バックグラウンド：

1 つの文字を追加、削除、または変更することで、1 つの単語を別の単語に変更できる場合は、2 つの単語を「隣接」と呼びます。

「単語リスト」は、連続する単語が隣接している一意の単語の順序付きリストです。

問題：

入力として 2 つの単語を取り、辞書をたどってそれらの間の単語のリストを作成するプログラムを作成します。

例:

hate  → love:     hate, have, hove, love
dogs  → wolves:   dogs, does, doles, soles, solves, wolves
man   → woman:    man, ran, roan, roman, woman
flour → flower:   flour, lour, dour, doer, dower, lower, flower

この問題にどのようにアプローチするかはよくわかりません。最初の試みでは、最初の単語の順列を作成し、その中の文字を置き換えようとしました。2 番目に考えたのは、サフィックス ツリーのようなものかもしれません。

少なくとも問題を分解するための考えやアイデアをいただければ幸いです。これは宿題ではなく、私が自分で取り組んでいるプログラミングの課題であることを覚えておいてください。

Answer 1

私はこれを自分で行い、それを使用して (あまり良くない) Windows ゲームを作成しました。

これをグラフとして実装するという他の人が推奨するアプローチを使用しました。ここで、各ノードは単語であり、1文字が異なる場合はそれらが接続されています。これは、よく知られているグラフ理論の結果を使用して、単語間のパスを見つけることができることを意味します (たとえば、距離 1 の単語を知ることで距離 2 の単語を見つけることができる単純な再帰)。

トリッキーな部分は、グラフを構築することです。悪いニュースは、それが O(n^2) であることです。幸いなことに、リアルタイムで実行する必要はありません。プログラムはファイルから辞書の単語を読み取るのではなく、以前に焼き付けたデータ構造を読み取ります。

重要な洞察は、順序は問題ではなく、実際には邪魔になるということです。順序情報を取り除き、単語をより簡単に比較できるようにする単語を保持する別のフォームを作成する必要があります。これは O(n) で行うことができます。たくさんの選択肢があります。2つ見せます。

1. 単語パズルでは、アナグラム辞書と呼ばれるエンコーディングをよく使用します。単語は、同じ文字をアルファベット順に並べた別の単語で表されます。したがって、「cars」は「acrs」になります。リストとスリットの両方が「ilsst」になります。これは元の単語よりも比較に適した構造ですが、はるかに優れた比較が存在します (ただし、他の単語パズルには非常に便利な構造です)。

2. 文字数。単語内でのその文字の頻度を示す 26 個の値の配列。したがって、「cars」の場合は 1,0,1,0,0 で始まります...「a」と「c」が 1 つずつあるためです。ゼロ以外のエントリ (単語にどの文字が表示されるか) の外部リストを保持して、26 ではなく最大で 5 または 6 の値をチェックするだけでよいようにします。カウントが違います。これは私が使用するものです。

だから、これが私がやった方法です。

上記のデータ構造を実装したプログラムを書きました。

WordNode というクラスがありました。これには元の単語が含まれています。文字が 1 つ異なる他のすべての WordNodes のリスト。各文字の頻度を示す 26 個の整数の配列、文字カウント配列内のゼロ以外の値のリスト。

イニシャライザは、文字頻度配列と対応するゼロ以外の値のリストを設定します。接続された WordNode のリストをゼロに設定します。

すべての単語に対して WordNode クラスのインスタンスを作成した後、compare メソッドを実行して、頻度カウントの違いが 2 箇所以内かどうかを確認します。これは通常、単語に文字が含まれている場合よりもわずかに少ない比較で済みます。悪くない。正確に 2 か所が異なる場合は、1 文字だけ異なるため、その WordNode を、1 文字だけ異なる WordNode のリストに追加します。

これは、1 文字異なるすべての単語のグラフが作成されたことを意味します。

データ構造全体をエクスポートするか、必要のない文字の頻度やその他のものを取り除いて保存することができます (私はシリアル化された XML を使用しました。そのようにする場合は、WordNodes のリストを参照として処理し、埋め込みオブジェクトではありません)。

実際のゲームは、このデータ構造を (辞書ではなく) 読み込むだけでよく、直接検索するだけで 1 文字異なる単語を本質的にゼロ時間で見つけることができます。

残念ながら私のゲームはがらくたでした。