これはインタビューの質問です。文字列 a を b に変換して、一度に 1 つのアルファベットのみを変更し、変更するたびに変換された文字列が辞書に登録されるようにする必要があります。最小数の変換でこれを行う必要があります。たとえば、cat-->boy からの変換は次のように実行できます。
cat-->bat-->bot-->boy (if dictionary has bat and bot)
この質問のために、プレフィックス ツリー (トライ) を作成することを考えることができますが、トライした後はどうすればよいかわかりません。誰かが可能なアプローチを提案できますか? ブルートフォースアプローチの使用を避けようとしています。
単一文字編集の最小数を計算する方法を知りたい場合は、レーベンシュタイン距離をご覧ください。ただし、これは、挿入、削除、および置換のみが許可されていることを前提としています。
たとえば、cat -> boy を変更すると、レーベンシュタイン距離は 3 になり、3 つの置換 (c->b、a->o、t->y) があります。
転置も許可されている場合は、ダメラウ・レーベンシュタイン距離を考慮する必要があります。
たとえば、cat -> cta のレーベンシュタイン距離は 2 で、ダメラウ–レーベンシュタイン距離は 1 です。
問題は既にプレフィックス トライに分割されています。
解決策に到達するには、さらにいくつかの手順を実行する必要があります。