126 Word Ladder II

126. Word Ladder II

1. Question

Given two words (beginWord and endWord), and a dictionary's word list, find all shortest transformation sequence(s) from beginWord to endWord, such that:
  1. 1.
    Only one letter can be changed at a time
  2. 2.
    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
["hit","hot","dot","dog","cog"],
3
["hit","hot","lot","log","cog"]
4
]
Copied!
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.

2. Implementation

(1) BFS + Backtracking
思路:
(1)利用BFS找到最短路径,和每个word的邻近的word
(2) 通过回溯法,找出所有的路径
1
class Solution {
2
public List<List<String>> findLadders(String beginWord, String endWord, List<String> wordList) {
3
List<List<String>> res = new ArrayList<>();
4
5
Set<String> dict = new HashSet<>(wordList);
6
Map<String, List<String>> neighbors = new HashMap<>();
7
Map<String, Integer> distance = new HashMap<>();
8
9
List<String> path = new ArrayList<>();
10
11
dict.add(beginWord);
12
13
getMinPathByBFS(beginWord, endWord, dict, neighbors, distance);
14
path.add(beginWord);
15
getAllPathsByDFS(beginWord, endWord, neighbors, distance, path, res);
16
return res;
17
}
18
19
public void getMinPathByBFS(String start, String end, Set<String> dict, Map<String, List<String>> neighbors, Map<String, Integer> distance) {
20
for (String word : dict) {
21
neighbors.put(word, new ArrayList<>());
22
}
23
24
Queue<String> queue = new LinkedList<>();
25
queue.add(start);
26
distance.put(start, 0);
27
boolean minLevel = false;
28
29
while (!queue.isEmpty() && !minLevel) {
30
int size = queue.size();
31
32
for (int i = 0; i < size; i++) {
33
String curWord = queue.remove();
34
int curDist = distance.get(curWord);
35
36
List<String> nextWords = getNeighbors(curWord, dict);
37
38
for (String nextWord : nextWords) {
39
neighbors.get(curWord).add(nextWord);
40
41
if (!distance.containsKey(nextWord)) {
42
distance.put(nextWord, curDist + 1);
43
44
if (nextWord.equals(end)) {
45
minLevel = true;
46
}
47
else {
48
queue.add(nextWord);
49
}
50
}
51
}
52
}
53
}
54
}
55
56
public List<String> getNeighbors(String word, Set<String> dict) {
57
List<String > res = new ArrayList<>();
58
char[] letters = word.toCharArray();
59
60
for (int i = 0; i < word.length(); i++) {
61
char oldC = letters[i];
62
63
for (char c = 'a'; c <= 'z'; c++) {
64
if (letters[i] == c) {
65
continue;
66
}
67
letters[i] = c;
68
69
String nextWord = new String(letters);
70
71
if (dict.contains(nextWord)) {
72
res.add(nextWord);
73
}
74
}
75
letters[i] = oldC;
76
}
77
return res;
78
}
79
80
public void getAllPathsByDFS(String start, String end, Map<String, List<String>> neighbors, Map<String, Integer> distance, List<String> path, List<List<String>> res) {
81
if (start.equals(end)) {
82
res.add(new ArrayList<String>(path));
83
return;
84
}
85
86
for (String neighbor : neighbors.get(start)) {
87
if (distance.get(neighbor) == distance.get(start) + 1) {
88
path.add(neighbor);
89
getAllPathsByDFS(neighbor, end, neighbors, distance, path, res);
90
path.remove(path.size() - 1);
91
}
92
}
93
}
94
}
Copied!

3. Time & Space Complexity

BFS + Backtracking: 时间复杂度? , 空间复杂度?