121.单词接龙 II

描述

给出两个单词（start和end）和一个字典，找出所有从start到end的最短转换序列
比如：
1.每次只能改变一个字母。
2.变换过程中的中间单词必须在字典中出现。

注意事项

1.所有单词具有相同的长度。
2.所有单词都只包含小写字母。

样例

给出数据如下：
start = "hit"
end = "cog"
dict = ["hot","dot","dog","lot","log"]

返回

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

思路

先从end出发做start的BFS，再从start出发做end的DFS，一边走一边保证距离越来越近，也可以倒过来做因为是无向图，所以只需要保证路径顺序就可以了，一个方向BFS另一个方向DFS

代码

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);

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

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

        return ladders;
    }

    // 从起点开始进行bfs，bfs对map和distance都进行了初始化
    private void bfs(Map<String, List<String>> map,
                     Map<String, Integer> distance,
                     String start,
                     String end,
                     Set <String> dict) {
        Queue<String> queue = new LinkedList<String>();
        queue.offer(start);
        distance.put(start, 0);
        // 给dict中每一个单词映射一个新的hash数组
        for (String s : dict) {
            map.put(s, new ArrayList<String>());
        }
        
        while(!queue.isEmpty()) {
            String crt = queue.poll();

            List<String> nextList = getNextList(crt, dict);
            for (String next : nextList) {
                // 将当前单词加入到下一个单词的地图中
                map.get(next).add(crt);
                // distance中未标记的结点，在distance中标好距离，加入队列
                if (!distance.containsKey(next)) {
                    distance.put(next, distance.get(crt) + 1);
                    queue.offer(next);
                }
            }
        }
    }

    // 将当前单词变为字典中存在的下一个单词(两个单词差一个字母)，将从起点到终点一条路线上的所有单词全部加入到list
    private List<String> getNextList(String crt, Set<String> dict) {
        List<String> list = new ArrayList<String>();

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

        return list;
    }
    
    // 注意起始位置的变换要体现在接口参数中,从终点开始进行dfs，crt代表的是队列中抛出的点，bfs运行到最后crt代表的是终点
    private void dfs(List<String> path,
                     Map<String, List<String>> map,
                     Map<String, Integer> distance,
                     String crt,
                     String start,
                     List<List<String>> ladders) {
        // crt是从end开始搜索的，所以当crt为start的时候，一条逆序的有效的路径已经出来了，那么这里把这条路径翻转一下，放到结果中，之后再翻转一下以便之后其他路径的搜索
        // 不可以把path.add(crt)加入到else里，因为每次递归都要remove，若写进else里并不会每次都把crt加入path，会造成动态数组下标越界
        path.add(crt);
        if (crt.equals(start)) {
            Collections.reverse(path);
            ladders.add(new ArrayList(path));
            // 若不翻转回来的话，当退出一层dfs，执行完path.remove(path.size() - 1);会移除错误的单词
            Collections.reverse(path);  
        } else {
            for (String next : map.get(crt)) {
                // 注意此处不是distance.get(next) == distance.get(crt) + 1，对下一个计算的单词要求是要distance里(并不是每个单词都在distance里)然后距离只有+1的差距
                if (distance.containsKey(next) && distance.get(crt) == distance.get(next) + 1) {
                    dfs(path, map, distance, next, start, ladders);
                }
            }
        }
        path.remove(path.size() - 1);
    }
}