[LeetCode] Word Ladder II

126. Word Ladder II

A transformation sequence from word beginWord to word endWord using a dictionary wordList is a sequence of words beginWord -> s1 -> s2 -> … -> sk such that:

  • Every adjacent pair of words differs by a single letter.
  • Every si for 1 <= i <= k is in wordList. Note that beginWord does not need to be in wordList.
  • sk == endWord

Given two words, beginWord and endWord, and a dictionary wordList, return all the shortest transformation sequences from beginWord to endWord, or an empty list if no such sequence exists. Each sequence should be returned as a list of the words [beginWord, s1, s2, …, sk].

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
86
87
88
89
90
91
92
93
94
95
class Solution {
unordered_map<string, vector<string>> g;
unordered_set<string> c;
int len = INT_MAX;
vector<vector<string>> res;
bool similar(string& s1, string& s2) { //o(k)
int diff = 0;
for(int i = 0; i < s1.length() and diff < 2; i++) {
if(s1[i] != s2[i]) diff++;
}
return diff == 1;
}

void buildG(vector<string>& w, string& begin) { //o(n^2)
for(int i = 0; i < w.size(); i++) {
for(int j = i + 1; j < w.size(); j++) {
if(similar(w[i], w[j])) {
g[w[i]].push_back(w[j]);
g[w[j]].push_back(w[i]);
}
}
}
if(!g.count(begin)) {
for(int i = 0; i < w.size(); i++) {
if(similar(begin,w[i]))
g[begin].push_back(w[i]);
}
}
}
void backTracking(string& cur, string& target, vector<string>& tmp) {
if(tmp.size() > len) return;
if(tmp.back() == target) {
if(tmp.size() < len) {
len = tmp.size();
res.clear();
}
res.push_back(tmp);
return;
}

for(auto nxt : g[cur]) {
if(c.count(nxt)) continue;
c.insert(nxt);
tmp.push_back(nxt);
backTracking(nxt, target, tmp);
tmp.pop_back();
c.erase(nxt);
}
}
void insert(unordered_map<string,int>& m, string& t) {
vector<string> ans(m.size() + 1);
ans[m.size()] = t;
for(auto [k, i] : m) {
ans[i] = k;
}
res.push_back(ans);
}
void bfs(string& st, string& t) {
queue<vector<string>> q;
unordered_set<string> v{st};
q.push({st});
while(res.empty()) {
int sz = q.size();
unordered_set<string> lv;
while(sz--) {
auto vec = q.front(); q.pop();
for(auto nxt : g[vec.back()]) {
if(v.count(nxt)) continue;
if(nxt == t) {
vec.push_back(nxt);
res.push_back(vec);
break;
} else {
lv.insert(nxt);
vec.push_back(nxt);
q.push(vec);
vec.pop_back();
}
}
}
v.insert(lv.begin(),lv.end());
}
}

public:
vector<vector<string>> findLadders(string beginWord, string endWord, vector<string>& wordList) {
buildG(wordList, beginWord);
if(!g.count(endWord)) return res;
vector<string> tmp{beginWord};
c.insert(beginWord);
bfs(beginWord, endWord);

return res;
}
};
Author: Song Hayoung
Link: https://songhayoung.github.io/2022/02/17/PS/LeetCode/word-ladder-ii/
Copyright Notice: All articles in this blog are licensed under CC BY-NC-SA 4.0 unless stating additionally.