単語の辞書と 2 つの文字列aとがありbます。
一度に 1 文字だけを変更し、すべての中間語が辞書にあることを確認して、a を b に変換するにはどうすればよいでしょうか?
例：
dictionary: {"cat", "bat", "hat", "bad", "had"}
a = "bat"
b = "had"
解決：
"bat" -> "bad" -> "had"
編集: 以下に示す解決策は、辞書の単語からグラフを作成して、すべての単語が 1 文字だけ異なる他のすべての単語に対して優位性を持つようにすることを提案しています。辞書が大きすぎる場合、これはやや難しいかもしれません (英語の単語だけを話しているわけではないとしましょう)。
また、これが許容できる場合でも、そのようなグラフを作成するための最適なアルゴリズムは何ですか? 単語から他のすべての単語へのエッジを見つけると、O(n) になります。ここで、n は辞書のサイズです。そして、合計グラフ構築はO（n2）になりますか？より良いアルゴリズムはありますか？
これは宿題ではなく、面接の質問です。