Gfrktyl

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_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.