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

For example,

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

Return

1
2
3
4
[
  ["hit","hot","dot","dog","cog"],
  ["hit","hot","lot","log","cog"]
]

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.

UPDATE (2017/1/20):
The wordList parameter had been changed to a list of strings (instead of a set of strings). Please reload the code definition to get the latest changes.

解法1：

这题挺繁琐的。思想不难，难的是优化。用到的几个知识点总结一下：
一个是建立邻接链表来给DFS使用，也就是说，先用一次bfs来遍历出字典中所有word的前驱word.　从start开始，第一步就找出所有能转换为start的word。以此类推。
同时，为了dfs中的优化，每一步时同时记录当前word能到达下一个word的最小步数。
这里用一个distance来记录。当开始跑dfs的时候，distance就可以用来判断下一个变化的word是不是最短路上的。
C++

1

Java

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
public class Solution {
    public List<List<String>> findLadders(String beginWord, String endWord, List<String> wordList) {
        List<List<String>> res = new ArrayList<List<String>>();
        Map<String, List<String>> map = new HashMap<String, List<String>>();
        Map<String, Integer> distance = new HashMap<String, Integer>();
        Set<String> dict = new HashSet<String>();
        for (String ss : wordList) {
            dict.add(ss);
        }
        if (!dict.contains(endWord)) {
            return res;
        }
        dict.add(beginWord);
        dict.add(endWord);
        List<String> ladder = new ArrayList<String>();
        bfs(map, distance, beginWord, endWord, dict);
        dfs(res, ladder, endWord, beginWord, map, distance);
        return res;
    }
    private 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);
        // Create an adjacent list
        for (String s : dict) {
            map.put(s, new ArrayList<String>());
        }
        while (!q.isEmpty()) {
            String current = q.poll();
            List<String> candidates = getCandidates(current, dict);
            for (String candidate : candidates) {
                map.get(candidate).add(current);    // reverse put
                // record the minimum length to the start point
                if (!distance.containsKey(candidate)) {
                    distance.put(candidate, distance.get(current) + 1);
                    q.offer(candidate);
                }
            }
        }
    }
    private void dfs(List<List<String>> res, List<String> ladder, String current, String start, Map<String, List<String>> map,
                    Map<String, Integer> distance) {
        ladder.add(current);
        if (current.equals(start)) {
            Collections.reverse(ladder);
            res.add(new ArrayList<String>(ladder));
            Collections.reverse(ladder);
        } else {
            for (String next : map.get(current)) {
                if (distance.containsKey(next) && distance.get(next) == distance.get(current) - 1) {
                    dfs(res, ladder, next, start, map, distance);
                }
            }
        }
        ladder.remove(ladder.size() - 1);
    }
    private List<String> getCandidates(String word, Set<String> wordList) {
        List<String> candidates = new ArrayList<String>();
        for (int i = 0; i < word.length(); i++) {
            for (char c = 'a'; c <= 'z'; c++) {
                if (c != word.charAt(i)) {
                    String modified = word.substring(0, i) + c + word.substring(i + 1);
                    if (wordList.contains(modified)) {
                        candidates.add(modified);
                        }                    
                }
            }
        }
        return candidates;
    }
}