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:
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.
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
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;
}
};
Code: C++ The above code can still be speeded up if we also begin fromend. Once we meet the same word fromstartandend, we know we are done. 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.