java - 単語の文字列を指定して、ワードラダーを作成できますか

Question

開始単語、目標単語、および使用が許可されている単語の文字列配列が与えられます。再帰を使用して、指定された文字列配列から少なくとも 1 つの単語を使用して、最初の単語と最後の単語の間に単語ラダーを構築できるかどうかを返すことになっています。

再帰は私にとって非常に難しいので、この問題にどのようにアプローチするかについて本当に迷ったり混乱したりしています。

Answer 1

再帰は、それ自体の内部から関数を呼び出すことにあります。常に終了条件を指定する必要があります (そうしないと、スタック オーバーフローが発生します)。残りはニーズによって異なります。

class Myclass {
    public static int doSomething(int a) {
        if (a < 10) {
             doSomething(a + 1);
        }
    }

    public static void main(String [] args) {
        System.out.printl(Myclass.doSomething(0));
    }
}

Answer 2

単語ごとに、考えられるすべての兄弟のリストにリンクします。次に、可能なすべてのはしごのツリーの構築を開始します...最初から始めます。ゴールにたどり着いた場合は、2 つの間のパスを返します。ツリーをナビゲートする際に再帰を使用できます。

Answer 3

@ user2103249 が言ったこと。このような場合、再帰ルーチンはおそらく成功したパスを返すはずです。次の順序で何か：

public String[] canFindPath(String[] pathSoFar) {
    for (characters in last word of pathSoFar) {
        for (all possible modifications of the character) {
            if (modifying the character produces a word in the word list but not already in pathSoFar) {
                Create new pathSoFar copy, with the one additional word;
                if (additionalWord == goalWord) {
                    return newPathSoFar;
                }
                String[] result = canFindPath(newPathSofar);
                if (result != null) return result;
             }
         }
     }
     return null;
}

十数の異なるアプローチがありますが。

最初に、単語リスト内の単語 A から単語 B への可能な遷移のマップを作成すると、各ステップでそれぞれを検索するのではなく、可能性をすばやく索引付けできるため、処理が高速化されます。