Ttykuu

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:

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.

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_wordnext_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: beginWordnendword:endWordnwordListwordList")
 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 space complexity in both solution is bad.