Word Ladder II

Given two words (beginWord and endWord), and a dictionary's word list, find all shortest transformation sequence(s) from beginWord to endWord, such that:

Only one letter can be changed at a time Each intermediate word must exist in the word list For example,

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

Note: All words have the same length.

All words contain only lowercase alphabetic characters.

Tips:

先BFS找长度，再DFS找所有路径。

1). Use BFS to find the shortest distance between start and end, tracing the distance of crossing nodes from start node to end node, and store node's next level neighbors to HashMap;

2). Use DFS to output paths with the same distance as the shortest distance from distance HashMap: compare if the distance of the next level node equals the distance of the current node + 1.

Code：

public class Solution {
    /**
      * @param start, a string
      * @param end, a string
      * @param dict, a set of string
      * @return a list of lists of string
      */
    public ArrayList<ArrayList<String>> findLadders(String start, String end, Set<String> dict) {
        // write your code here  
        dict.add(start);
        dict.add(end);
        ArrayList<ArrayList<String>> result = new ArrayList<>();
        HashMap<String, ArrayList<String>> map = new HashMap<>();
        HashMap<String, Integer> distance = new HashMap<>();
        BFS(start, end, dict, distance, map);
        ArrayList<String> path = new ArrayList<>();
        DFS(start, end,  path, distance, map, result);
        return result;
    }

    private void BFS(String start, String end, Set<String> dict, HashMap<String, Integer> distance,                             HashMap<String, ArrayList<String>> map) {
        Queue<String> queue = new LinkedList<>();
        queue.add(start);
        int length = 0;
        int depth = Integer.MAX_VALUE;
        distance.put(start, 0);
        for (String s : dict) {
            map.put(s, new ArrayList<String>());
        }
        while (!queue.isEmpty()) {
            if (length == depth) {
                return;
            }
            length++;
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                String word = queue.remove();
                for (String newWord : changeChar(dict, word)) {
                    if (newWord.equals(end)) {
                        depth = length;
                    }
                    map.get(newWord).add(word);
                    if (!distance.containsKey(newWord)) {
                        distance.put(newWord, distance.get(word) + 1);
                        queue.offer(newWord);
                    }
                }
            }
        }
    }

    private void DFS(String start, String end, ArrayList<String> path, HashMap<String, Integer> distance, 
                     HashMap<String, ArrayList<String>> map, ArrayList<ArrayList<String>> result) {
        path.add(end);
        if (end.equals(start)) {
            Collections.reverse(path);
            result.add(new ArrayList<String>(path));
            Collections.reverse(path);
        } else {
            for (String s : map.get(end)) {
                if (distance.containsKey(s) && distance.get(s) +1 == distance.get(end)) {
                    DFS(start, s, path, distance, map, result);
                }
            }
        }
        path.remove(path.size() - 1);
    }


    private ArrayList<String> changeChar(Set<String> dict, String word) {
        ArrayList<String> result = new ArrayList<>();
        for (char c = 'a'; c <= 'z'; c++) {
            for (int i = 0; i < word.length(); i++) {
                String newWord = replace(i, c, word);
                if (dict.contains(newWord)) {
                    result.add(newWord);
                }
            }
        }
        return result;
    }

    private String replace(int i, char c, String word) {
        char[] chars = word.toCharArray();
        chars[i] = c;
        return new String(chars);
    }

}