## 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:

1. Only one letter can be changed at a time.
2. 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:

1. BFS: Generate the qualified permutation, add distance by 1, until find the answer or queue is empty
2. Optimizations:
1. Python:
1. 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,
1. 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.
1. Removing entries in S from T vs Creating new entries from S if it is not in T.
2. C++

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 = word
#   item = 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, wordList):
if candidate == endWord:
return q_item + 1
elif candidate in seen:
continue
q.append([candidate, q_item + 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)

# 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:
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:]:
except:
continue
return nextSet

steps, wordLen = 2, len(beginWord)
front, back = set([beginWord]), set([endWord])
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 from`end`. Once we meet the same word from`start`and`end`, 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 pointers`phead`and`ptail`save a lot of time. At each round of BFS, depending on the relative size of`head`and`tail`, we point`phead`to 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;

tail.insert(endWord);
int dist = 2;
while (!head.empty() && !tail.empty()) {
if (head.size() <= tail.size()) {
ptail = &tail;
}
else {
}
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