Given two words (beginWord_and_endWord), and a dictionary's word list, find all shortest transformation sequence(s) frombeginWord_to_endWord, such that:

1. Only one letter can be changed at a time
2. Each transformed word must exist in the word list. Note that _beginWord _is _not _a transformed word.

Note:

• Return an empty list if there is no such transformation sequence.
• All words have the same length.
• All words contain only lowercase alphabetic characters.
• You may assume no duplicates in the word list.
• You may assume _beginWord _and _endWord _are non-empty and are not the same.

Backtracking，会超时

class Solution {
    private int len = Integer.MAX_VALUE;

    public List<List<String>> findLadders(String beginWord, String endWord, List<String> wordList) {
        List<List<String>> res = new ArrayList<>();
        HashSet<String> set = new HashSet<String>();
        HashSet<String> visited = new HashSet<>();
        for(String word: wordList)
            set.add(word);

        if(!set.contains(endWord))
            return res;

        ArrayList<String> line = new ArrayList<String>();
        line.add(beginWord);

        helper(res, line, set, visited, 0, beginWord, endWord);

        return res;
    }

    public void helper(List<List<String>> res, List<String> line, HashSet<String> set, HashSet<String> visited, int step, String curr, String end) {
        if(curr.equals(end)) {            
            if(step < len) {
                res.clear();
                len = step;
            }
            res.add(new ArrayList<String>(line));
            return;
        }

        if(step >= len) 
            return;

        char[] cs = curr.toCharArray();
        for(int i = 0; i < cs.length; i++) {
            char origin = cs[i];

            for(char c = 'a'; c <= 'z'; c++) {
                if(c == origin)
                    continue;

                cs[i] = c;
                String s = String.valueOf(cs);
                if(set.contains(s) && !visited.contains(s)) {
                    visited.add(s);
                    line.add(s);
                    helper(res, line, set, visited, step + 1, s, end);
                    line.remove(line.size() - 1);
                    visited.remove(s);
                }

                cs[i] = origin;
            }
        }
    }
}

BFS，运行速度比较慢，只战胜了0.99%的用户。这里面有两个值得注意的点，1）什么时候停止BFS，2）如何去重，去重只是在把node出队之后才标记，否则会导致一些path被忽略

class Solution {
    class Node {
        public String str;
        public Node last;

        public Node(String str) {
            this.str = str;
        }
    }

    public List<List<String>> findLadders(String beginWord, String endWord, List<String> wordList) {
        List<List<String>> res = new ArrayList<>();
        HashSet<String> set = new HashSet<String>();
        HashSet<String> visited = new HashSet<>();
        for(String word: wordList)
            set.add(word);

        if(!set.contains(endWord))
            return res;

        set.remove(beginWord);
        LinkedList<Node> curr = new LinkedList<>();
        LinkedList<Node> next = new LinkedList<>();
        curr.offer(new Node(beginWord));

        while(curr.size() > 0) {
            Node temp = curr.poll();
            visited.add(temp.str);

            if(temp.str.equals(endWord)) {
                Node end = temp;
                List<String> solution = new ArrayList<>();

                while(end != null) {
                    solution.add(end.str);
                    end = end.last;
                }
                Collections.reverse(solution);
                res.add(solution);
            } else {
                char[] cs = temp.str.toCharArray();

                for(int i = 0; i < cs.length; i++) {
                    char origin = cs[i];

                    for(char c = 'a'; c <= 'z'; c++) {
                        if(c == origin)
                            continue;
                        cs[i] = c;
                        String s = String.valueOf(cs);

                        if(set.contains(s) && !visited.contains(s)) {
                            Node node = new Node(s);
                            node.last = temp;
                            next.offer(node);
                        }
                    }

                    cs[i] = origin;
                }
            }

            if(curr.size() == 0 && res.size() == 0) {
                curr = next; 
                next = new LinkedList<>();
            }
        }

        return res;
    }
}