I am working on Word Ladder - LeetCode
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.
Approach 1: Breadth First Search
class Solution1:
def ladderLength(self, beginWord, endWord, wordList):
"""
:type beginWord: str
:type endWord: str
:type wordList: List[str]
:rtype step: int
"""
visited = set()
wordSet = set(wordList)
queue = [(beginWord, 1)]
while len(queue) > 0: #queue is not empty
word, step = queue.pop(0)
#logging.debug(f"word: {word}, step:{step}")
#base case
if word == endWord:
return step #get the result.
if word in visited: #better than multiple conditions later.
continue
#visited.add(word) # paint word as visited
#traverse all the variants
for i in range(len(word)):
for j in range(0, 26):
ordinal = ord('a') + j
next_word = word[0:i] + chr(ordinal) + word[i + 1:]
#logging.debug(f"changed_word: {next_word}")
if next_word in wordSet:
queue.append((next_word, step + 1)) #contiue next stretch
visited.add(word) # paint word as visited
return 0
Runtime: 740 ms, faster than 22.79% of Python3 online submissions for Word Ladder.
Memory Usage: 15.9 MB, less than 13.09% of Python3 online submissions for Word Ladder.
Approach 2: Bidirectional Breadth First Search
class Solution2(object):
def ladderLength(self, beginWord, endWord, wordList):
#base case
if (endWord not in wordList) or (not endWord) or (not beginWord) or (not wordList):
return 0
size = len(beginWord)
word_set = set(wordList)
forwards, backwards = {beginWord}, {endWord}
visited = set()
step = 0
while forwards and backwards:
step += 1 #treat the first word as step 1
if len(forwards) > len(backwards):
forwards, backwards = backwards, forwards #switch process
#logging.debug(f"step: {step}, forwards: {forwards}, backwords: {backwards}")
neighbors= set()
for word in forwards:#visit words on this level
if word in visited: continue
for i in range(size):
for c in 'abcdefghijklmnopqrstuvwxyz':
next_word = word[:i] + c + word[i+1:]
if next_word in backwards: return step + 1 #terminating case
if next_word in word_set: neighbors.add(next_word)
#logging.debug(f"next_word{next_word}, step: {step}")
visited.add(word) #add visited word as the final step
forwards = neighbors
#logging.debug(f"final: {step}")
return 0
Runtime: 80 ms, faster than 98.38% of Python3 online submissions for Word Ladder.
Memory Usage: 13.6 MB, less than 28.37% of Python3 online submissions for Word Ladder.
TestCase
class MyCase(unittest.TestCase):
def setUp(self):
self.solution = Solution2()
def test_1(self):
beginWord = "hit"
endWord = "cog"
wordList = ["hot","dot","dog","lot","log","cog"]
#logging.debug(f"beginWord: {beginWord}\nendword:{endWord}\nwordList{wordList}")
check = self.solution.ladderLength(beginWord, endWord, wordList)
answer = 5
self.assertEqual(check, answer)
def test_2(self):
beginWord = "hit"
endWord = "cog"
wordList = ["hot","dot","dog","lot","log"]
check = self.solution.ladderLength(beginWord, endWord, wordList)
answer = 0
self.assertEqual(check, answer)
The memory usage in both solution is bad.