[Geeks for Geeks] Word Ladder I

Word Ladder I

Given two distinct words startWord and targetWord, and a list denoting wordList of unique words of equal lengths. Find the length of the shortest transformation sequence from startWord to targetWord.

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.

The second 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
class Solution {
bool connected(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;
}
public:
int wordLadderLength(string startWord, string targetWord, vector<string>& wordList) {
if(startWord == targetWord) return 1;
unordered_map<string, int> mp;
mp[startWord] = 1;
int no = 2;
for(auto& word : wordList) {
if(mp.count(word)) continue;
mp[word] = no++;
}
if(!mp.count(targetWord)) return 0;
int goal = mp[targetWord];
vector<vector<int>> adj(no + 1);

for(auto i = begin(mp); i != end(mp); i++) {
for(auto j = next(i); j != end(mp); j++) {
if(connected(i->first, j->first)) {
adj[i->second].push_back(j->second);
adj[j->second].push_back(i->second);
}
}
}

vector<int> vis(no + 1, 0);
queue<int> q;
q.push(1);
vis[1] = 1;
while(!q.empty()) {
auto u = q.front(); q.pop();
for(auto& v : adj[u]) {
if(v == goal) return vis[u] + 1;
if(vis[v]) continue;
vis[v] = vis[u] + 1;
q.push(v);
}
}

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