3

データ構造プロジェクトの場合、「cat」と「dog」のような 2 つの単語の間の最短経路を見つける必要がありますが、一度に 1 文字しか変更できません。トライを実装することでそれを実行しようとしています。最短経路探索を実装できないようです。

猫 -> ベビーベッド -> 歯車 -> 犬

すべての単語は同じ長さになり、辞書ファイルから入力しています。私たちは言葉から言葉へと移動しなければなりません。したがって、その間の単語は有効な単語でなければなりません。

トライでは無理だと思うのですが、どなたかご存知ないでしょうか？

4

3 に答える 3

5

VP-Treeを使用したい場合 、アルゴリズムはレーベンシュタイン距離と呼ばれます AC 実装はここにあります。コードが長すぎて回答として投稿できません:
C VP-Tree

于 2013-03-08T17:42:00.643 に答える
1

この種の問題のより良いデータ構造はグラフです。これはことばの梯子と呼ばれ、ここで調べることができます：http: //en.wikipedia.org/wiki/Word_ladder。

于 2013-03-08T17:43:31.300 に答える
-2

あなたが求めているのは単純な BFS です。各単語はグラフの頂点ですが、グラフを作成する必要さえありません。単語の配列を使用して解決できます。

words = {"cat", "dog", "dot", "cot"}
mark = {0, 0, 0, 0}
distance = {0, 0, 0, 0}
queue Q
start_word_index = 0; // words[0] -> "cat"
destination_word_index = 1; // words[1] -> "dog"
Q.push(start_word_index)
while(Q is not empty) {
    word_index = Q.pop()
    for each `words[j]` {
        if (difference between `words[word_index]` and `words[j]` is only 1 character) AND
           (`mark[j]` is not 1) {
            mark[j] = 1
            Q.push(j)
            distance[j] = distance[word_index] + 1
        }
    }
}

if mark[destination_word_index] is 0 {
    print "Not reachable"
} else {
    print "Distance is ", distance[destination_word_index]
}
于 2013-03-08T18:37:10.193 に答える