Given two words (beginWord and endWord), and a dictionary's word list, find the length of shortest transformation sequence from beginWord 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.

For example,

Given:
beginWord="hit"
endWord="cog"
wordList=["hot","dot","dog","lot","log","cog"]

Return

  [
    ["hit","hot","dot","dog","cog"],
    ["hit","hot","lot","log","cog"]
  ]

Note:

• Return 0 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.

Solution: 先从end做bfs到start，hashmap记录到各单词的distance。然后从start做dfs到end, 取distance依次减少1的路径

    public List<List<String>> findLadders(String start, String end, List<String> dict) {
        List<List<String>> ans = new ArrayList<>();
        if(dict == null || dict.size() == 0){
            return ans;
        }
        List<String> wordlist = new ArrayList<String>();
        wordlist.add(start);

        if(start.equals(end)){
            ans.add(wordlist);
            return ans;
        }
        Set<String> dicts = new HashSet<>();
        for (String word : dict) {
            dicts.add(word);
        }
        if (!dicts.contains(end)) {
            return ans;
        }
        //记得加start
        dicts.add(start);        
        Map<String, Integer> hashmap = new HashMap<String, Integer>();
        bfs(end, start, dicts, hashmap);
        dfs(start, end, dicts, ans, wordlist, hashmap);
        return ans;
    }
    private void bfs(String end, String start, Set<String> dict, Map<String, Integer> hashmap){
        Queue<String> queue = new LinkedList<String>();
        int length = 0;
        queue.add(end);
        hashmap.put(end, length);

        while(!queue.isEmpty()){

            int size = queue.size();
            length++;

            for(int i = 0; i < size; i++){
                String word = queue.poll();

                for(String nextword : nextWord(word, dict)){
                    if(hashmap.containsKey(nextword)){
                        continue;
                    }
                    queue.add(nextword);
                    hashmap.put(nextword, length);
                }
            }
        }
    }
    private void dfs(String start, String end, Set<String> dict, List<List<String>> result, List<String> path, Map<String, Integer> hashmap){
        if(start.equals(end)){
            result.add(new ArrayList<String>(path));
            return;
        }
        for(String nextword : nextWord(start, dict)){
            if(hashmap.get(nextword) + 1 == hashmap.get(start)){
                path.add(nextword);
                dfs(nextword, end, dict, result, path, hashmap);
                path.remove(path.size() - 1);
            }
        }
    }
    private ArrayList<String> nextWord(String word, Set<String> dict){
        ArrayList<String> nextWord = new ArrayList<String>();
        for(int i = 0; i < word.length(); i++){
            for(char c = 'a'; c <= 'z'; c++){
                if(c == word.charAt(i)){
                    continue;
                }
                String newWord = replace(word, i, c);
                if(dict.contains(newWord)){
                    nextWord.add(newWord);
                }
            }
        }
        return nextWord;
    }

    private String replace(String word, int i, char c){
        StringBuilder sb = new StringBuilder(word);
        sb.setCharAt(i, c);
        return sb.toString();
    }