Difficulty: Medium

Frequency: N/A

Given two words (beginWord and endWord), and a dictionary’s word list, find the length of shortest transformation sequence from beginWord to endWord, such that:

1. Only one letter can be changed at a time
2. Each intermediate word must exist in the word list

For example,

Given:
beginWord = `"hit"`
endWord = `"cog"`
wordList = `["hot","dot","dog","lot","log"]`

As one shortest transformation is `"hit" -> "hot" -> "dot" -> "dog" -> "cog"`,
return its length `5`.

Note:

• Return 0 if there is no such transformation sequence.
• All words have the same length.
• All words contain only lowercase alphabetic characters.

Test Cases:

Solution 1:

Data structure:
Steps:
Complexity:
Runtime:
Space:
Code:
```class Solution {
public:
int ladderLength(string beginWord, string endWord, unordered_set<string>& wordList) {
wordList.insert(endWord);
queue<string> toVisit;
int dist = 2;
while (!toVisit.empty()) {
int n = toVisit.size();
for (int i = 0; i < n; i++) {
string word = toVisit.front();
toVisit.pop();
if (word == endWord) return dist;
}
dist++;
}
}
private:
void addNextWords(string word, unordered_set<string>& wordList, queue<string>& toVisit) {
wordList.erase(word);
for (int i = 0; i < (int)word.size(); i++) {
char c = word[i];
for (int j = 0; j < 26; j++) {
word[i] = 'a' + j;
if (wordList.find(word) != wordList.end()) {
toVisit.push(word);
wordList.erase(word);
}
}
word[i] = c;
}
}
};
```

Solution 2:

Data structure:
steps:
Complexity:
Runtime:
Space:
Code:

Submission errors:

Things to learn: