What can I do to make it faster?


  • 0
    S

    Simple BFS logic, it times out on some inputs

    class Solution(object):
        def ladderLength(self, beginWord, endWord, wordList):
            """
            :type beginWord: str
            :type endWord: str
            :type wordList: List[str]
            :rtype: int
            """
    
            def nextWords(word, wordList):
                result = []
                n = len(word)
                for i in range(n): # replace i th character in word
                    for ch in 'abcdefghijklmnopqrstuvwxyz': # with "ch"
                        newWord = word[:i] + ch + word[i + 1:]
                        if newWord in wordList and newWord != word: # as long as new word is not same as existing word and new word is valid
                            result.append(newWord) # append to list of next options
                            wordList.remove(newWord) # remove to prevent revisiting same word again
    
                return result
    
            q = []
            q.append( (beginWord,1) ) # append begin word
            
            if beginWord in wordList:
                wordList.remove(beginWord) 
    
            while len(q) > 0:
                x,level = q.pop(0)
    
                if x == endWord:  # did we find end word?
                    return level
    
                children = nextWords(x, wordList) # get list of children in bfs tree?
    
                if not children and len(q) <= 0: # if no more children and queue is empty too, return 0
                    return 0
    
                for child in children:
                    q.append((child,level+1)) # enqueue all children
    
            return 0

  • 0
    S

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.