LeetCode(126) -- Word Ladder II

Problem

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 transformed word must exist in the word list. Note that beginWord is not a transformed word. 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. Example 1:

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

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

The Best Solution

这道题是一道有向无环图寻找最短路径的题。

每个单词都相当于图中的一个节点，如果两个单词之间只差一个字母，那个这两个节点就视为互相连通的。理论上这种连通是没有方向的，比如”dog”可以变成”log”,同样的，”log”也可以变成”dog”。但实际上，就这道题而言，有起始点和结束点，寻找最短路径时，我们当然不希望往回走，所以我们要构建一个有方向的图。

寻找图的最短路径，当然是要用bfs。为了提高效率，我们可以从两端向中间凑，直到相遇为止。原理是中间的节点会比较多，如果从一个方向找，那个需要查找的节点会越来越多。但是如果从起始点开始找的同时，也从结束点往回找，需要遍历的节点会大大减少。

答案中使用reverse来标记是否是往回找。bfs的最终目标是形成一个map,只包含最短路径，其他节点我们不关心。

最后，通过dfs或者backtracking的方法，把所有的最短路径添加到答案中。

class Solution {
    public List<List<String>> findLadders(String beginWord, String endWord, List<String> wordList) {
        List<List<String>> res = new ArrayList<>();
        Set<String> dict = new HashSet<>(wordList);
        if (!dict.contains(endWord)) {
            return res;
        }
        Map<String, List<String>> map = new HashMap<>();
        Set<String> startSet = new HashSet<>();
        Set<String> endSet = new HashSet<>();
        endSet.add(endWord);
        startSet.add(beginWord);
        
        bfs(startSet, endSet, map, dict, false);
        
        List<String> list = new ArrayList<>();
        list.add(beginWord);
        dfs(res, list, beginWord, endWord, map);
        return res;
    }
    
    private void bfs(Set<String> startSet, Set<String> endSet, Map<String, List<String>> map, Set<String> dict, boolean reverse) {
        if (startSet.size() == 0) return;
        if (startSet.size() > endSet.size()) {
            bfs(endSet, startSet, map, dict, !reverse);
            return;
        }
        
        Set<String> tmp = new HashSet<>();
        dict.removeAll(startSet);
        boolean finish = false;
        
        for (String s : startSet) {
            char[] chs = s.toCharArray();
            for (int i = 0; i < chs.length; i++) {
                char old = chs[i];
                for (char c = 'a'; c <= 'z'; c++) {
                    chs[i] = c;
                    String word = new String(chs);
                    
                    if (dict.contains(word)) {
                        if (endSet.contains(word)) {
                            finish = true;
                        } else {
                            tmp.add(word);
                        }
                        
                        String key = reverse ? word : s;
                        String val = reverse ? s : word;
                        
                        if (map.get(key) == null) {
                            map.put(key, new ArrayList<>());
                        }
                        
                        map.get(key).add(val);
                    }
                }
                chs[i] = old;
            }
        }
        if (!finish) {
            bfs(tmp, endSet, map, dict, reverse);
        }
    }
    
    private void dfs(List<List<String>> res, List<String> list, String word, String endWord, Map<String, List<String>> map) {
        if (word.equals(endWord)) {
            res.add(new ArrayList(list));
            return;
        }
        if (map.get(word) == null) return;
        for (String next : map.get(word)) {
            list.add(next);
            dfs(res, list, next, endWord, map);
            list.remove(list.size() - 1);
        }
    }
}