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
| unordered_map<string, unordered_set<string>> adj;
bool check(string& A, string& B) {
int diff = 0;
for(int i = 0; i < A.length() and diff <= 1; i++) diff += (A[i] != B[i]);
return diff == 1;
}
void connect(string& A, string& B) {
adj[A].insert(B);
adj[B].insert(A);
}
void dfs(vector<vector<string>>& res, vector<string>& cur, unordered_set<string>& vis, string end) {
if(!res.empty() and res[0].size() < cur.size()) return;
if(cur.back() == end) {
if(!res.empty() and res[0].size() > cur.size()) res.clear();
res.push_back(cur);
return;
}
for(auto& v : adj[cur.back()]) {
if(vis.count(v)) continue;
vis.insert(v);
cur.push_back(v);
dfs(res,cur,vis,end);
vis.erase(v);
cur.pop_back();
}
}
vector<vector<string> > Solution::findLadders(string start, string end, vector<string>& dict) {
adj.clear();
vector<vector<string>> res;
for(int i = 0; i < dict.size(); i++) {
if(check(start, dict[i])) connect(start,dict[i]);
if(check(end, dict[i])) connect(end,dict[i]);
for(int j = i + 1; j < dict.size(); j++) {
if(check(dict[i], dict[j])) connect(dict[i], dict[j]);
}
}
if(check(start, end)) connect(start,end);
dfs(res, vector<string>() = {start}, unordered_set<string>() = {start}, end);
return res;
}
|
