私は次の質問を解決しようとしています。最短コストの単語変換
あなたには、開始語、辞書、および終了語が与えられます。 4つの操作を実行できます。
これらの操作のすべてのコストは異なる場合があります。
制約：すべての中間の文字は、開始語と終了語とともに辞書に存在する必要があります。これを達成するための最小限のコストを見つけてください。
戻り値-1が返されない場合、
お願いします。
制約の詳細（単語の最大長や辞書の最大単語数など）を教えてください。
しかし、私はあなたにその問題を解決する1つの解決策を教えてあげます。
まず、グラフを作成できます。各ノードはあなたが作ることができる単語（辞書で）であり、エッジはあなたができる操作です。
すべての辺は入力から与えられる重みを持っています。次に、開始単語から辞書のすべての単語までの距離を保存する必要があります。 C++では、map<string, int>を宣言できます。
このマップのキーはノード文字列であり、そのマップの値は最初の単語からの距離です。
次に、dijkstraのような最短距離アルゴリズムを使用できます。開始点は最初の単語で、終了点は作成したい単語です。 Dijkstraはいつもの始点を持つ最速のアルゴリズムなので、私があなたの場合は使用します。
次に、時間の複雑さを計算しましょう。
のは、すべての単語の最大長はSで、辞書の単語の最大数は、すべての操作ではN.
であるあなたには、いくつかの文字の位置を変更したり、追加したり削除した場合、それはO（S）をとりましょう単語の後ろを除くいくつかの位置の文字と、文字を変更するだけの場合はO（1）。
とにかく時間の複雑さはすべてO（SNlgN）です。グラフのノードの最大数は、私たちが現在持っている単語から辞書に単語を作ることができるならば、もはや現在のノードからエッジを作ることはできません。
エッジの最大数はO（N）cuzです。最大でもすべてのノードで4つのエッジを作成できます。したがって、ヒープを持つDijkstraの時間の複雑さを知っているなら、それは簡単です。
David Davidありがとうございます。問題文では、単語の最大長や辞書の最大単語数については何も制約がありません。また、Javaでは、特に挿入、削除、置換（文字列が不変であるため）はO（S）をとり、Sは文字列の長さであり、これを実行するとすべての単語に対してO（S^2）になります。私はJavaでこのアルゴリズムを試してみましたが、少なくとも20分で結果は得られませんでした。私は良い方法があるはずだと確信しています。 –
私は、あなたが制約について（単語の最大長や辞書の最大単語数など）詳細を教えてください。 しかし、私はあなたにその問題を解決する方法を教えてあげます。 まず、グラフを作成できます。各ノードはあなたが作ることができる単語（辞書で）であり、エッジはあなたができる操作です。すべての辺には入力から与えられる重みがあります。 C++では、マップ<string, int>を宣言できます。そのマップのキーはノードストリングであり、そのマップの値は最初の単語からの距離です。 次に、dijkstraのような最短距離アルゴリズムを使用できます。 Dijkstraはいつもの始点を持つ最速のアルゴリズムなので、私があなたの場合は使用します。次に、時間の複雑さを計算しましょう。すべての単語の最大長をSとし、辞書の単語の最大数をNとしましょう。すべての操作で、一部の文字の位置を変更したり、前後の文字を追加または削除したりする場合は、O（S）単語の
これまでに何を試しましたか？ – Pyves
「すべてのコストは異なる可能性があり、指定されています」 問題の複雑さが増しすぎると感じています。すべての費用が1であれば、ここからどこで始めるべきか分かります。 –
頂点が辞書内の単語であり、重み付けされたエッジが1つの単語から他の単語に至る操作であるグラフ上の単純な最短経路探索のように聞こえる。 – Henry