127. Word Ladder
Given two words (beginWord_and_endWord), and a dictionary's word list, find the length of shortest transformation sequence frombeginWord_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.
Thoughts:
- BFS: Generate the qualified permutation, add distance by 1, until find the answer or queue is empty
- Optimizations:
- Python:
- Character flopping: flop (expanding the transformation candidate in the "front" set, then check whether it is in the word dictionary: T: O(M*26*L*L); O(L) . M: Dictionary Size, L: word length,
- Dictionary Checking: Checking whether a word in current wordDictionary can be transformed into current word in the set: T:O(MNL). N: number of words in the dictionary.
- Removing entries in S from T vs Creating new entries from S if it is not in T.
- C++
- Python:
Code
class Solution(object):
def ladderLength(self, beginWord, endWord, wordList):
"""
:type beginWord: str
:type endWord: str
:type wordList: List[str]
:rtype: int
"""
def generateNeighbors(word, wordList):
for i in range(len(word)):
for letter in string.ascii_lowercase:
candidate = word[:i] + letter + word[i+1:]
if candidate in wordList:
yield candidate
# We use q to keep track of the next nodes to process in the BFS.
# Each item in the queue is a list with two items:
# item[0] = word
# item[1] = steps to reach word + 1 (i.e. number of nodes in list of nodes
# traversed to reach word - (format of Word Ladder I output)).
q = collections.deque([ [beginWord,1] ])
# We keep track of words we've processed to avoid getting stuck in a loop.
seen = set([beginWord])
# wordList is given as a list but we want O(1) lookup so we convert to a set.
wordList = set(wordList)
while q:
q_item = q.popleft()
for candidate in generateNeighbors(q_item[0], wordList):
if candidate == endWord:
return q_item[1] + 1
elif candidate in seen:
continue
seen.add(candidate)
q.append([candidate, q_item[1] + 1])
return 0
class Solution(object):
def ladderLength(self, beginWord, endWord, wordList):
"""
:type beginWord: str
:type endWord: str
:type wordList: List[str]
:rtype: int
"""
dist = 2
n = len(beginWord)
wordDict = set(wordList)
wordDict.discard(beginWord)
# corner case: since we assume endWord is in wordDict when doing the swapping
if endWord not in wordDict:
return 0
front, back = set([beginWord]), set([endWord])
while front:
# generate all valid permutations
front = wordDict & set([word[:i] + c + word[i+1:]
for word in front
for i in range(len(word))
for c in string.ascii_lowercase
])
if front & back:
# there are common elements in front and back, done
return dist
dist += 1
if len(front) > len(back):
# swap front and back for better performance (fewer choices in generating nextSet)
front, back = back, front
# remove transformations from wordDict to avoid cycle
wordDict -= front
return 0
Code: Python Optimization
class Solution:
# @param {string} beginWord
# @param {string} endWord
# @param {set<string>} wordDict
# @return {integer}
def ladderLength(self, beginWord, endWord, wordDict):
def generateNextSet1(current, wordDict, wordLen):
nextSet = set()
for word in current:
for index in range(wordLen):
for ch in 'abcdefghijklmnopqrstuvwxyz':
nextWord = word[:index] + ch + word[index+1:]
if nextWord in wordDict:
nextSet.add(nextWord)
return nextSet
def generateNextSet2(current, wordDict):
nextSet = set()
for word in current:
for nextWord in wordDict:
index = 0
try:
while word[index] == nextWord[index]:
index += 1
if word[index+1:] == nextWord[index+1:]:
nextSet.add(nextWord)
except:
continue
return nextSet
steps, wordLen = 2, len(beginWord)
front, back = set([beginWord]), set([endWord])
wordDict.discard(beginWord)
switchThreshold = 26*wordLen
while front:
# get all valid transformations
if len(wordDict) >= switchThreshold:
front = generateNextSet1(front, wordDict, wordLen)
else:
front = generateNextSet2(front, wordDict)
if front & back:
# there are common elements in front and back, done
return steps
steps += 1
if len(front) >= len(back):
# swap front and back for better performance (smaller nextSet)
front, back = back, front
# remove transformations from wordDict to avoid cycles
if (len(wordDict)>>1) >= len(front):
# s.difference_update(t): O(len(t))
wordDict -= front
else:
# s.difference(t): O(len(s))
wordDict = wordDict - front
return 0
Code: C++ OptimizationThe above code can still be speeded up if we also begin fromend. Once we meet the same word fromstartandend, we know we are done.This link provides a nice two-end search solution. I rewrite the code below for better readability. Note that the use of two pointerspheadandptailsave a lot of time. At each round of BFS, depending on the relative size ofheadandtail, we pointpheadto the smaller set to reduce the running time.
class Solution {
public:
int ladderLength(string beginWord, string endWord, vector<string>& wordList) {
unordered_set<string> wordDict (wordList.begin(), wordList.end());
if (wordDict.find(endWord) == wordDict.end()) return 0;
unordered_set<string> head, tail, *phead, *ptail;
head.insert(beginWord);
tail.insert(endWord);
int dist = 2;
while (!head.empty() && !tail.empty()) {
if (head.size() <= tail.size()) {
phead = &head;
ptail = &tail;
}
else {
phead = &tail;
ptail = &head;
}
unordered_set<string> temp;
for (auto itr = phead -> begin(); itr != phead -> end(); itr++) {
string word = *itr;
for (int p = 0; p < (int)word.length(); p++) {
char letter = word[p];
for (int k = 0; k < 26; k++) {
word[p] = 'a' + k;
if (ptail -> find(word) != ptail -> end())
return dist;
if (wordDict.find(word) != wordDict.end()) {
temp.insert(word);
wordDict.erase(word);
}
}
word[p] = letter;
}
}
dist++;
// throw away the expaned and add in new candidate into set
*phead = temp;
}
return 0;
}
};