Given two words (beginWordandendWord), and a dictionary's word list, find all shortest transformation sequence(s) frombeginWordtoendWord, 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 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.

UPDATE (2017/1/20):
ThewordListparameter had been changed to a list of strings (instead of a set of strings). Please reload the code definition to get the latest changes.

tag: word ladder, BFS, DFS

class Solution {
    public List<List<String>> findLadders(String beginWord, String endWord, List<String> wordList) {
        List<List<String>> ans = new ArrayList<>();
        if (wordList == null || wordList.size() == 0) return ans;
        Set<String> dict = new HashSet<>();
        for (String word : wordList){
            dict.add(word);
        }
        if (!dict.contains(endWord)) return ans;

        Map<String, Integer> distance = new HashMap<>();
        Map<String, Set<String>> path = new HashMap<>();

        distance.put(beginWord, 1);
        for (String word : dict){
            path.put(word, new HashSet<>());
        }

        bfs(beginWord, endWord, dict, path, distance);
        //System.out.println("distance after bfs: " + String.valueOf(distance));
        List<String> temp = new ArrayList<>();
        temp.add(endWord);
        dfs(beginWord, endWord, distance, path, temp, ans);

        return ans;
    }

    private void bfs(String beginWord, String endWord, Set<String> dict, Map<String, Set<String>> path, Map<String, Integer> distance){
        Queue<String> q = new LinkedList<>();
        q.offer(beginWord);

        while (!q.isEmpty()){
            int size = q.size();

            for (int i = 0; i < size; i++){
                String cur = q.poll();

                if (cur.equals(endWord)) return;

                for (String newCur : newWords(cur, dict)){
                    path.get(newCur).add(cur);
                    if (distance.get(newCur) != null) continue;
                    distance.put(newCur, distance.get(cur) + 1);
                    q.offer(newCur);
                }

            }
        }
    }

    private void dfs(String target, String source, Map<String, Integer> distance, Map<String, Set<String>> path, List<String> temp, List<List<String>> ans){
        if (source.equals(target)){
            //System.out.println("found: " + String.valueOf(temp));
            Collections.reverse(temp);
            ans.add(new ArrayList<String>(temp));
            Collections.reverse(temp);
            return;
        }

        for (String newWord : path.get(source)){
            if (distance.containsKey(newWord) && distance.get(newWord) + 1 == distance.get(source)){
                temp.add(newWord);
                dfs(target, newWord, distance, path, temp, ans);
                temp.remove(temp.size() - 1);
            }
        }
    }

    private List<String> newWords(String word, Set<String> dict){
        List<String> ans = new ArrayList<>();

        for (int i = 0; i < word.length(); i++){
            for (char c = 'a'; c <= 'z'; c++){
                String newWord = word.substring(0, i) + c + word.substring(i + 1);
                if (!dict.contains(newWord) || ans.contains(newWord)) continue;

                ans.add(newWord);
            }
        }

        return ans;
    }
}