Word Ladder II

Given two words (start and end), and a dictionary, find all shortest transformation sequence(s) from start to end, such that:

Only one letter can be changed at a time

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:

这道题的难点就是求出所有的最短路径的解决方案，可以使用BFS来求解，但是为了套用模版，使一般的题目都可以模式化，要知道很多面试这个题没做过，需要做3，4个小时，结果面试过程中需要半个小时做完，所以我跟人的方法就是尽量选择容易记忆，容易总结，容易成为模版的方法，所以碰见了球解决方案个数的，我多半使用DFS,但是这道题直接使用DFS是很不直接的，可以先设置两个集合，一个是保持所有单词的出入度的哈希表，一个是从开始的节点到当前节点的距离。然后在做DFS。利用临时变量path, 从后往前的添加，这个题我自己没有做出来，职能搬运九张算法的方案了。

Map = {hit=[hot], cog=[dog, log], hot=[hit, dot, lot], lot=[hot, dot, log], dog=[dot, log, cog], log=[lot, dog, cog], dot=[hot, lot, dog]}

distance = {hit=0, cog=4, lot=2, hot=1, dog=3, log=3, dot=2}

public class Solution {
    public List<List<String>> findLadders(String start, String end,
            Set<String> dict) {
        List<List<String>> ladders = new ArrayList<List<String>>();
        Map<String, List<String>> map = new HashMap<String, List<String>>();
        Map<String, Integer> distance = new HashMap<String, Integer>();

        dict.add(start);
        dict.add(end);

        bfs(map, distance, start, end, dict);

        System.out.println(map);

        List<String> path = new ArrayList<String>();

        dfs(ladders, path, end, start, distance, map);


        return ladders;
    }

    void dfs(List<List<String>> ladders, List<String> path, String crt,
            String start, Map<String, Integer> distance,
            Map<String, List<String>> map) {
        path.add(crt);
        if (crt.equals(start)) {
            Collections.reverse(path);
            ladders.add(new ArrayList<String>(path));
            Collections.reverse(path);
        } else {
            for (String next : map.get(crt)) {
                if (distance.containsKey(next) && distance.get(crt) == distance.get(next) + 1) { 
                    dfs(ladders, path, next, start, distance, map);
                }
            }           
        }
        path.remove(path.size() - 1);
    }

    void bfs(Map<String, List<String>> map, Map<String, Integer> distance,
            String start, String end, Set<String> dict) {
        Queue<String> q = new LinkedList<String>();
        q.offer(start);
        distance.put(start, 0);
        for (String s : dict) {
            map.put(s, new ArrayList<String>());
        }

        while (!q.isEmpty()) {
            String crt = q.poll();

            List<String> nextList = expand(crt, dict);
            for (String next : nextList) {
                map.get(next).add(crt);
                if (!distance.containsKey(next)) {
                    distance.put(next, distance.get(crt) + 1);
                    q.offer(next);
                }
            }
        }
    }

    List<String> expand(String crt, Set<String> dict) {
        List<String> expansion = new ArrayList<String>();

        for (int i = 0; i < crt.length(); i++) {
            for (char ch = 'a'; ch <= 'z'; ch++) {
                if (ch != crt.charAt(i)) {
                    String expanded = crt.substring(0, i) + ch
                            + crt.substring(i + 1);
                    if (dict.contains(expanded)) {
                        expansion.add(expanded);
                    }
                }
            }
        }

        return expansion;
    }
}