Word Ladder II
unique words of equal lengths. Find all shortest transformation sequence(s) from startWord to targetWord. You can return them in any order possible.
Keep the following conditions in mind:
- A word can only consist of lowercase characters.
- Only one letter can be changed in each transformation.
- Each transformed word must exist in the wordList including the targetWord.
- startWord may or may not be part of the wordList.
- Return an empty list if there is no such transformation sequence.
The first part of this problem can be found here.
- Time : O(|wordList| |wordList| n + v + e)
- Space : O(|wordList| + e)
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
| class Solution {
bool conn(string& a, string& b) {
int diff = 0;
for(int i = 0; i < a.length() and diff < 2; i++) {
if(a[i] != b[i]) diff++;
}
return diff == 1;
}
void dfs(vector<string>& wordList, vector<string>& build, int u, int start, vector<vector<int>>& adj, vector<vector<string>>& res) {
build.push_back(wordList[u]);
if(u == start) {
vector<string> push = build;
reverse(begin(push), end(push));
res.push_back(push);
} else {
for(auto& v : adj[u]) {
dfs(wordList, build, v, start, adj, res);
}
}
build.pop_back();
}
public:
vector<vector<string>> findSequences(string beginWord, string endWord, vector<string>& wordList) {
int start, end, n = wordList.size();
bool endInc = false, startInc = false;
for(auto& w : wordList) {
if(w == beginWord) startInc = true;
else if(w == endWord) endInc = true;
}
if(!startInc) wordList.push_back(beginWord);
if(!endInc) wordList.push_back(endWord);
n = wordList.size();
vector<vector<int>> adj(n);
vector<vector<int>> path(n);
for(int i = 0; i < n; i++) {
if(wordList[i] == beginWord) start = i;
else if(wordList[i] == endWord) end = i;
for(int j = i + 1; j < n; j++) {
if(conn(wordList[i], wordList[j])) {
adj[i].push_back(j);
adj[j].push_back(i);
}
}
}
queue<int> q;
q.push(start);
path[start].push_back(-1);
while(!q.empty() and path[end].empty()) {
int sz = q.size();
unordered_map<int, vector<int>> tmp;
while(sz--) {
auto u = q.front(); q.pop();
for(auto& v : adj[u]) {
if(path[v].size()) continue;
tmp[v].push_back(u);
}
}
for(auto pair : tmp) {
path[pair.first] = pair.second;
q.push(pair.first);
}
}
vector<vector<string>> res;
dfs(wordList, vector<string>() = {}, end, start, path, res);
return res;
}
};
|
