Description

Given two words (startandend), and a dictionary, find all shortest transformation sequence(s) fromstarttoend, such that:

1. Only one letter can be changed at a time
2. Each intermediate word must exist in the dictionary

Notice

• All words have the same length.
• All words contain only lowercase alphabetic characters.

Example

Given:
start="hit"
end="cog"
dict=["hot","dot","dog","lot","log"]
Return

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

Solution

需要两个信息：list<node, List of node's neighbors>, map<node, distance>
用dfs来求得这两个信息。distance 记录成离start的distance而不是离end的，这样超出最小路径范围的点根本不会被记录下来

"hot"
"dog"
["hot","cog","dog","tot","hog","hop","pot","dot"]

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 List<List<String>> findLadders(String start, String end, Set<String> dict) {
        // write your code here
        HashMap<String, List<String>> neighbors = new HashMap<String, List<String>>();
        Queue<String> queue = new LinkedList<String>();
        dict.remove(start);
        queue.add(start);
        int distance = dfs(end, dict, queue, neighbors);

        List<List<String>> result = new ArrayList<List<String>>();
        List<String> path = new ArrayList<String>();
        path.add(start);
        bfs(end, path, result, neighbors, distance);
        return result;
    }

    private int dfs(String end, Set<String> dict, Queue<String> queue, HashMap<String, List<String>> neighbors) {
        int distance = 1;
        while (!queue.isEmpty()) {
            int size = queue.size();
            distance++;    
            for (int index = 0; index < size; index++) {
                String cur = queue.poll();
                neighbors.put(cur, new ArrayList<String>());
                for (int i = 0; i < cur.length(); i++) {
                    for (char c = 'a'; c <= 'z'; c++) {
                        String newStr = replace(cur, i, c);
                        if (newStr.equals(end)) {
                            neighbors.get(cur).add(end);
                            return distance;
                        }

                        if (dict.contains(newStr)) {
                            neighbors.get(cur).add(newStr);
                            queue.offer(newStr);
                            dict.remove(newStr);
                        }
                    }
                }
            }
        }

        return 0;
    }

    private void bfs(String end, List<String> path, List<List<String>> result, HashMap<String, List<String>> neighbors, int distance) {
        if (path.size() == distance) {
            if (path.get(path.size() - 1).equals(end)) {
                result.add(new ArrayList<String>(path));
            } 

            return;
        }

        String prev = path.get(path.size() - 1);
        if (neighbors.containsKey(prev)) {
            for (String s : neighbors.get(prev)) {
                path.add(s);
                bfs(end, path, result, neighbors, distance);
                path.remove(path.size() - 1);
            }
        }
    }

    private String replace(String str, int index, char c) {
        return str.substring(0, index) + c + str.substring(index + 1);
    }
}