codekofi
← All questions

Word Ladder

HardGraphs

The problem

Given a start word, a target word and a dictionary, change the start into the target one letter at a time, where every intermediate word must be in the dictionary.

Return the number of words in the shortest such chain, counting both ends, or 0 if no chain exists.

ladderLength("hit", "cog", {"hot","dot","dog","lot","log","cog"})

One of these three is correct

Two lines apart, at the closest.

The wrong ones are this same code with between two and five lines changed. Some of those changes do not compile. There is no Run button: running all three would turn this into a vote rather than a reading.

1int ladderLength(const string& beginWord, const string& endWord,
2 const vector<string>& wordList) {
3
4 unordered_set<string> pool(wordList.begin(), wordList.end());
5
6 if (!pool.count(endWord)) {
7 return 0;
8 }
9
10 queue<string> edge;
11
12 int steps = 0;
13
14 while (!edge.empty()) {
15
16 int wide = edge.size();
17
18 for (int i = 0; i < wide; i++) {
19
20 string word = edge.front();
21 edge.pop();
22
23 if (word == endWord) {
24 return steps;
25 }
26
27 for (int j = 0; j < (int)word.size(); j++) {
28
29 char had = word[j];
30
31 for (char c = 'a'; c <= 'z'; c++) {
32
33 word[j] = c;
34
35 if (pool.count(word)) {
36 pool.erase(word);
37 edge.push(word);
38 }
39 }
40
41 word[j] = had;
42 }
43 }
44
45 steps++;
46 }
47
48 return 0;
49}
1int ladderLength(const string& beginWord, const string& endWord,
2 const vector<string>& wordList) {
3
4 unordered_set<string> pool(wordList.begin(), wordList.end());
5
6 if (!pool.count(endWord)) {
7 return 0;
8 }
9
10 queue<string> edge;
11
12 int steps = 1;
13
14 while (!edge.empty()) {
15
16 int wide = edge.size();
17
18 for (int i = 0; i < wide; i++) {
19
20 string word = edge.front();
21 edge.pop();
22
23 if (!(word == endWord)) {
24 return steps;
25 }
26
27 for (int j = 0; j < (int)word.size(); j++) {
28
29 char had = word[j];
30
31 for (char c = 'a'; c <= 'z'; c++) {
32
33 word[j] = c;
34
35 if (pool.count(word)) {
36 pool.erase(word);
37 edge.push(word);
38 }
39 }
40
41 word[j] = had;
42 }
43 }
44
45 steps++;
46 }
47
48 return 0;
49}
1int ladderLength(const string& beginWord, const string& endWord,
2 const vector<string>& wordList) {
3
4 unordered_set<string> pool(wordList.begin(), wordList.end());
5
6 if (!pool.count(endWord)) {
7 return 0;
8 }
9
10 queue<string> edge;
11 edge.push(beginWord);
12
13 int steps = 1;
14
15 while (!edge.empty()) {
16
17 int wide = edge.size();
18
19 for (int i = 0; i < wide; i++) {
20
21 string word = edge.front();
22 edge.pop();
23
24 if (word == endWord) {
25 return steps;
26 }
27
28 for (int j = 0; j < (int)word.size(); j++) {
29
30 char had = word[j];
31
32 for (char c = 'a'; c <= 'z'; c++) {
33
34 word[j] = c;
35
36 if (pool.count(word)) {
37 pool.erase(word);
38 edge.push(word);
39 }
40 }
41
42 word[j] = had;
43 }
44 }
45
46 steps++;
47 }
48
49 return 0;
50}