java - 给定一串单词，你能构造一个wordladder吗

Question

我得到了一个起始词、一个目标词和一个允许使用的词的字符串数组。我应该使用递归来返回是否可以使用给定字符串数组中的至少一个单词在第一个单词和最后一个单词之间构造一个单词阶梯。

递归对我来说非常具有挑战性，所以对于如何解决这个问题，我真的很迷茫/困惑。

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

对于每个单词，将其链接到所有可能的同级列表。然后开始构建所有可能的梯子树......从第一个开始。如果您达到目标，则返回两者之间的路径。您可以在导航树时使用递归。

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;
}

尽管有十几种不同的方法。

最初在单词列表中构建从 wordA 到 wordB 的可能转换映射会加快速度，因为您可以快速索引所有可能性，而不必在每个步骤中搜索每个可能性。