[Work@] Word Ladder

Word Ladder

You are given two words - beginWord and endWord. You also have a wordList of size n.
All words are of the same length.

You have to create a transformation sequence from beginWord to endWord that looks like this:
beginWord → str1 → str2 → str3 → … → strk

Adjacent pairs in the sequence differ by a single character, and all strings from str1 to strk lie in wordList.

Also strk = endWord.

Find the minimum number of words in the shortest possible transformation sequence. If such a sequence is not possible return 0.

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
bool near(string& a, string& b) {
int i = 0, diff = 0, n = a.length();
while(i < n and diff <= 1) {
if(a[i] != b[i]) diff++;
i++;
}
return i == n and diff == 1;
}

int shortestLadderLength(string beginWord, string endWord,
vector<string> &wordList) {
unordered_map<string, vector<string>> adj;
int n = wordList.size();
for(int i = 0; i < n; i++) {
for(int j = 0; j < n; j++) {
if(near(wordList[i], wordList[j])) {
adj[wordList[i]].push_back(wordList[j]);
adj[wordList[j]].push_back(wordList[i]);
}
}
if(near(wordList[i], beginWord)) {
adj[wordList[i]].push_back(beginWord);
adj[beginWord].push_back(wordList[i]);
}
if(near(wordList[i], endWord)) {
adj[wordList[i]].push_back(endWord);
adj[endWord].push_back(wordList[i]);
}
}

if(near(beginWord, endWord)) {
return 2;
}

unordered_set<string> vis{beginWord};
queue<string> q;
q.push(beginWord);
int res = 2;

while(!q.empty()) {
int sz = q.size();
while(sz--) {
auto u = q.front(); q.pop();
for(auto& v : adj[u]) {
if(vis.count(v)) continue;
vis.insert(v);
q.push(v);
if(v == endWord) return res;
}
}
res++;
}

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