My code:

public class Solution {
    private class wordNode {
        String s;
        int step;
        wordNode pre;
        wordNode(String s, int step, wordNode pre) {
            this.s = s;
            this.step = step;
            this.pre = pre;
        }
    }
    
    public List<List<String>> findLadders(String beginWord, String endWord, Set<String> wordList) {
        List<List<String>> ret = new ArrayList<List<String>>();
        Queue<wordNode> q = new LinkedList<wordNode>();
        q.offer(new wordNode(beginWord, 1, null));
        Set<String> visited = new HashSet<String>();
        Set<String> unvisited = wordList;
        unvisited.add(endWord);
        int prevStep = 0;
        int minStep = 0;
        while (!q.isEmpty()) {
            wordNode node = q.poll();
            int currStep = node.step;
            if (node.s.equals(endWord)) {
                if (minStep == 0) {
                    minStep = currStep;
                }
                if (currStep == minStep) {
                    List<String> path = new ArrayList<String>();
                    while (node != null) {
                        path.add(0, node.s);
                        node = node.pre;
                    }
                    ret.add(path);
                }
                continue;
            }
            if (prevStep < currStep) {
                unvisited.removeAll(visited);
            }
            prevStep = currStep;
            char[] arr = node.s.toCharArray();
            for (int i = 0; i < arr.length; i++) {
                for (char c = 'a'; c <= 'z'; c++) {
                    char temp = arr[i];
                    arr[i] = c;
                    String newWord = String.valueOf(arr);
                    if (unvisited.contains(newWord)) {
                        q.offer(new wordNode(newWord, currStep + 1, node));
                        visited.add(newWord);
                    }
                    arr[i] = temp;
                }
            }
            
        }
        return ret;
    }
}

reference:
http://www.programcreek.com/2014/06/leetcode-word-ladder-ii-java/

Leetcode 最經(jīng)典的一道題目险胰，就這樣被我糟蹋了递瑰。。

和 I 相比没宾，有三個(gè)變化蒜埋。
為了追蹤淫痰。每個(gè) wordNode 結(jié)點(diǎn)有一個(gè) pre 指針，指向他的上一個(gè)結(jié)點(diǎn)整份。

minStep 用來保證待错，step最小的時(shí)候，才能把string插入 ret 中

I 中烈评，當(dāng)我發(fā)現(xiàn)一個(gè)string contained in set,就會(huì)把這個(gè)string從set中刪去朗鸠，因?yàn)槲覀冎恍枰业揭粋€(gè)最優(yōu)解。為了加快速度础倍，就把他刪了烛占。這樣其他排在后面的最優(yōu)解，就不能繼續(xù)遍歷下去了沟启。
但是這道題忆家，我們要找到所有解。所以德迹，只有當(dāng) 當(dāng)前 step全部遍歷完后芽卿，才能把他們用到的string全部刪除了。那如果以后其他的string需要用到他們呢胳搞？
這個(gè)時(shí)候卸例，這些string的step已經(jīng)不是最小了。

Anyway, Good luck, Richardo! -- 09/27/2016