127. Word Ladder

一个词要经过多少步才能变换成另一个词，每次只能变换一个字母。

我本来的思路是，先计算出wordList中所有词的“差异度”，比如abc和abb的差异度是1，abc和aaa的差异度是2。这样会形成一个巨大的图，顶点是所有的词，如果两个词的差异度是1，就会有边相连，表示这两个词可以直接互相转换。接下来只要遍历这个图，找到某两个顶点的最短路径就可以了。这个过程有点类似于建索引。

但是计算这个图的过程毫无疑问是O(N^2)，必定会TLE的。。。

后来发现，没必要计算所有的词。我不需要知道任意两个词之间的最短路径，只要关心beginWord和endWord就可以。而且，题目限定所有的词都是小写字母，所以一个词经过一次变换后，最多只有(25*词的长度)种可能，是可以穷举出来的。于是就有了下面的解法，本质上是从beginWord开始的一次BFS，每次尝试变换一个字母，看这个词是否在wordList中，最终可以形成一颗以beginWord为根节点的树。如果在这颗树的第n层的节点里发现了endWord，那就直接返回n，因为不可能有更小的值了，树只会越来越深。

代码：

public class Solution {
    public int ladderLength(String beginWord, String endWord, List<String> wordList) {
        Set<String> allWords = new HashSet<String>();

        // 如果endWord在词典中不存在，可以直接返回0
        boolean endWordExist = false;
        for (String word : wordList) {
            if (endWord.equals(word))
                endWordExist = true;
            // 其实我觉得wordList里如果有beginWord，应该直接返回0，但testcase不是这么设计的。。
            if (!beginWord.equals(word))
                allWords.add(word);
        }

        // bad case
        if (!endWordExist)
            return 0;

        // 题目限定needSteps不可能是0，wordList里也不可能有重复
        int needSteps = diff(beginWord, endWord);
        // 说明beginWord可以一步变为endWord
        if (needSteps == 1)
            return 2;
        // bad case
        if (wordList.size() < needSteps)
            return 0;

        // 开始BFS，每一层最多可能有26个节点，小写字母的a-z
        Set<String> nextWords = new HashSet<String>();
        Set<String> existWords = new HashSet<String>();
        nextWords.add(beginWord);
        // 总共要经过几轮迭代才能到达endWord？
        int tmp = bfs(nextWords, 1, existWords, allWords, endWord);
        return tmp == 0 ? 0 : tmp + 1;
    }

    private int diff(String word1, String word2) {
        int diff = 0;
        for (int i = 0; i < word1.length(); i++) {
            if (word1.charAt(i) != word2.charAt(i))
                diff++;
        }
        return diff;
    }

    /**
     * <p>bfs，“自顶向下”建立一个树，“逐层”扩展</p>
     *
     * @param nextWords 要扩展哪些词
     * @param step 当前是第几轮迭代
     * @param existWords 目前总共有那些词被使用过
     * @param allWords 所有可用的词
     * @param endWord 结束词
     * @return
     */
    private int bfs(Set<String> nextWords, int step, Set<String> existWords, Set<String> allWords, String endWord) {
        // 没有要继续遍历的节点了
        if (nextWords.size() == 0)
            return 0;

        // 这一层总共有哪些节点？
        Set<String> allChildren = new HashSet<String>();

        for (String next : nextWords) {
            // next这个词下面，可能有哪些词？
            Set<String> children = new HashSet<String>();
            char[] charArray = next.toCharArray();
            // 暴力穷举所有可能的词
            for (int i = 0; i < charArray.length; i++) {
                for (char c = 'a'; c <= 'z'; c++) {
                    // 每次替换一个字母，最多也就26个子节点
                    char old = charArray[i];
                    charArray[i] = c;
                    String tmp = new String(charArray);
                    charArray[i] = old;

                    if (tmp.equals(endWord))
                        return step;
                    if (allWords.contains(tmp) && !existWords.contains(tmp))
                        children.add(tmp);
                }
            }
            allChildren.addAll(children);
        }

        existWords.addAll(allChildren);
        return bfs(allChildren, step + 1, existWords, allWords, endWord);
    }
}

我的代码虽然能AC，但怎么这么长啊。。。