# 127. Word Ladder
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:
- Only one letter can be changed at a time.
- Each transformed word must exist in the word list. Note that beginWord is not a transformed word.
Note:
- Return 0 if there is no such transformation sequence.
- All words have the same length.
- All words contain only lowercase alphabetic characters.
- You may assume no duplicates in the word list.
- You may assume beginWord and endWord are non-empty and are not the same.
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.
# Solution
Approach 1: one-directional BFS. Time: O(N * L)
where N == len(wordList)
and L == len(beginWord)
.
Approach 2: bi-directional BFS.
# Code (Python)
Approach 1:
def ladderLength(self, beginWord, endWord, wordList):
"""
:type beginWord: str
:type endWord: str
:type wordList: List[str]
:rtype: int
"""
word_list = set(wordList)
if endWord not in word_list or len(beginWord) != len(endWord):
return 0
cur_words = [beginWord]
level = 1
while cur_words:
level += 1
# accumulate words at the next level
new_words = []
for word in cur_words:
# can also enumerate the whole word_list to see if diff == 1, but it takes N*L time
# this takes 26 * L time
for i in range(len(word)):
for letter in 'abcdefghijklmnopqrstuvwxyz':
if letter == word[i]:
continue
new_word = ''.join([word[:i], letter, word[i+1:]])
if new_word in word_list:
if new_word == endWord:
return level
# deduplication: mark as visited to avoid cycles
word_list.remove(new_word)
new_words.append(new_word)
cur_words = new_words
return 0
Approach 2:
def ladderLength(self, beginWord, endWord, wordList):
word_list = set(wordList)
if endWord not in word_list or len(beginWord) != len(endWord):
return 0
if beginWord == endWord:
return 1
# dedup: need to make sure the front tier (to be explored) is not in word_list
word_list.discard(beginWord)
front, back = set([beginWord]), set([endWord]) # use set operations as much as possible
level = 2
while front:
front = word_list & set([
''.join([word[:i], letter, word[i+1:]])
for i in range(len(beginWord))
for word in front
for letter in 'abcdefghijklmnopqrstuvwxyz'
])
if front & back: # has intersection
return level
level += 1
if len(back) < len(front):
front, back = back, front
# also dedup: exclude the front tier, but the back tier need to be included otherwise we can't find intersections
word_list -= front
return 0
# Code (C++)
Approach 1:
// BFS.
class Solution {
private:
bool isTransformable(string a, string b)
{
if (a.size() != b.size())
return false;
int count = 0;
for (int i = 0; i < a.size(); ++i)
{
if (a[i] != b[i])
count++;
if (count > 1)
return false;
}
return count == 1;
}
public:
int ladderLength(string beginWord, string endWord, vector<string>& wordList) {
bool visited[wordList.size()] = {false};
queue<string> q;
q.push(beginWord);
int level = 1;
while (!q.empty())
{
level++;
int qSize = q.size();
for (int i = 0; i < qSize; ++i)
{
string curr = q.front();
q.pop();
for (int j = 0; j < wordList.size(); ++j)
{
if (!visited[j] && isTransformable(curr, wordList[j]))
{
if (wordList[j] == endWord)
return level;
q.push(wordList[j]);
visited[j] = true;
}
}
}
}
return 0;
}
};
Approach 2:
// Bidirectional BFS.
class Solution {
private:
bool isTransformable(string a, string b)
{
if (a.size() != b.size())
return false;
int count = 0;
for (int i = 0; i < a.size(); ++i)
{
if (a[i] != b[i])
count++;
if (count > 1)
return false;
}
return count == 1;
}
public:
int ladderLength(string beginWord, string endWord, vector<string>& wordList) {
int i;
for (i = 0; i < wordList.size(); ++i)
{
if (wordList[i] == endWord)
break;
}
if (i == wordList.size())
return 0;
int visited[wordList.size()] = {0};
visited[i] = 2; // endWord is already visited.
queue<string> q1, q2;
q1.push(beginWord);
q2.push(endWord);
int level1 = 1;
int level2 = 1;
while (!q1.empty() && !q2.empty())
{
int q1Size = q1.size();
for (int i = 0; i < q1Size; ++i)
{
string curr = q1.front();
q1.pop();
for (int j = 0; j < wordList.size(); ++j)
{
if (visited[j] != 1 && isTransformable(curr, wordList[j]))
{
if (visited[j] == 2)
return level1 + level2;
q1.push(wordList[j]);
visited[j] = 1;
}
}
}
level1++;
int q2Size = q2.size();
for (int i = 0; i < q2Size; ++i)
{
string curr = q2.front();
q2.pop();
for (int j = 0; j < wordList.size(); ++j)
{
if (visited[j] != 2 && isTransformable(curr, wordList[j]))
{
if (visited[j] == 1)
return level1 + level2;
q2.push(wordList[j]);
visited[j] = 2;
}
}
}
level2++;
}
return 0;
}
};