How to improve my python code? It takes more than 800ms although it's accepted...


  • 0
    from sets import Set
    
    class Solution(object):
        def ladderLength(self, beginWord, endWord, wordDict):
            """
            :type beginWord: str
            :type endWord: str
            :type wordDict: Set[str]
            :rtype: int
            """
            wordDict.add(endWord)
            
            queue = [beginWord]
            stepMap = {beginWord : 1} #record how deep where a loop is
            
            while queue:
                query = queue[0]
                length = len(query)
                for i in range(0, length):
                    alphabets = [ch for ch in 'abcdefghijklmnopqrstuvwxyz' if ch != query[i]]
                    for alphabet in alphabets:
                        altered_query = ''
                        
                        if length == 1:
                            altered_query = alphabet
                        elif i == 0:
                            altered_query = alphabet + query[1:]
                        elif i == length - 1:
                            altered_query = query[:-1] + alphabet
                        else:
                            altered_query = query[:i] + alphabet + query[i+1:]
                            
                        if altered_query in wordDict:
                            if altered_query == endWord:
                                return stepMap[query] + 1
                            queue.append(altered_query)
                            stepMap[altered_query] = stepMap[query] + 1
                            wordDict.discard(altered_query)
                queue.pop(0) # delete query   
            return 0

Log in to reply
 

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