出力はホップ/ジャンプの最小数を示す数字です

Question

ターミナルコンソール/ UIから入力を受け取り、コンソール/ UIで出力するアプリケーションを作成します。

第1入力 - 3文字の単語のリスト。 2番目の入力 - 上記のリストから1語。 3番目の入力 - リストの別の単語。

出力は、2番目の入力から3番目の入力に到達できるホップ/ジャンプの最小数を示す数字です。すべてのホップ/ジャンプには次の規則があります。 1.すべてのホップ/ジャンプでは、一度に1つの文字しか変更できません。 2.結果の単語がリストに含まれている必要があります。 例：

第1入力= ["cat"、 "cii"、 "sim"、 "xim"、 "yep"、 "syd"、 "pol"、 "sit"、 "sii" 、 "飽和"、 "CIT"] 2入力は= "CAT" 3入力= "SII"

ホップ/パスをジャンプ：

"CAT" - > "CIT" - > "CII" - > "SII"

出力 - 4

Answer 1

あなたはBFSを使用してこの問題を解決することができます。

各入力文字列をノードに変換するだけで済みます。

ノードのすべてのペアについて、正確に1文字だけが異なる場合は、Edgeと接続します。

次に、BFSアルゴリズムを実行して、最短パスを見つけることができます。