Given two words beginWord and endWord, and a dictionary wordList, return the length of the shortest transformation sequence from beginWord to endWord, such that:
- Only one letter can be changed at a time.
- Each transformed word must exist in the word list.
Return 0 if there is no such transformation sequence.
Example 1:
Input: beginWord = "hit", endWord = "cog", wordList = ["hot","dot","dog","lot","log","cog"] Output: 5 Explanation: As one shortest transformation is "hit" -> "hot" -> "dot" -> "dog" -> "cog", return its length 5.
Example 2:
Input: beginWord = "hit", endWord = "cog", wordList = ["hot","dot","dog","lot","log"] Output: 0 Explanation: The endWord "cog" is not in wordList, therefore no possible transformation.
Constraints:
1 <= beginWord.length <= 100endWord.length == beginWord.length1 <= wordList.length <= 5000wordList[i].length == beginWord.lengthbeginWord,endWord, andwordList[i]consist of lowercase English letters.beginWord != endWord- All the strings in
wordListare unique.
Related Topics:
Breadth-first Search
Similar Questions:
Since we are looking for the shortest path, BFS should be our first option.
Given a word w, we can try to change each w[i] to a character from 'a' to 'z'.
Once we found a neighbor word v, we remove v from the word list and push it to the queue.
In the worst case we need to visit all the N words in A. For each word, we check all its 26W neighbors, and copy them to queue (the copying takes O(W) time), so addNeighbors takes O(W^2) time.
Thus, overall it takes O(N * W^2) time
// OJ: https://leetcode.com/problems/word-ladder/
// Author: github.com/lzl124631x
// Time: O(N * W^2)
// Space: O(NW)
class Solution {
void addNeighbors(string &w, queue<string> &q, unordered_set<string> &s) {
for (int i = 0; i < w.size(); ++i) {
char c = w[i];
for (char j = 'a'; j <= 'z'; ++j) {
if (w[i] == j) continue;
w[i] = j;
if (s.count(w)) {
q.push(w);
s.erase(w);
}
}
w[i] = c;
}
}
public:
int ladderLength(string B, string E, vector<string>& A) {
unordered_set<string> s(begin(A), end(A));
if (s.count(E) == 0) return 0;
queue<string> q;
q.push(B);
int ans = 1;
while (q.size()) {
int cnt = q.size();
while (cnt--) {
auto w = q.front();
q.pop();
if (w == E) return ans;
addNeighbors(w, q, s);
}
++ans;
}
return 0;
}
};// OJ: https://leetcode.com/problems/word-ladder/
// Author: github.com/lzl124631x
// Time: O(N * W^2)
// Space: O(NW)
class Solution {
public:
int ladderLength(string B, string E, vector<string>& A) {
unordered_set<string> head, tail, s(begin(A), end(A));
if (s.count(E) == 0) return 0;
head.insert(B);
tail.insert(E);
s.erase(B);
s.erase(E);
int ans = 2;
while (head.size() && tail.size()) {
if (head.size() > tail.size()) swap(head, tail);
unordered_set<string> tmp;
for (auto w : head) {
for (int i = 0; i < w.size(); ++i) {
char c = w[i];
for (char j = 'a'; j <= 'z'; ++j) {
w[i] = j;
if (tail.count(w)) return ans;
if (s.count(w)) {
tmp.insert(w);
s.erase(w);
}
}
w[i] = c;
}
}
++ans;
head = tmp;
}
return 0;
}
};