TLE of BFS, ask for help.


  • 0
    P
    class Solution(object):
        def findLadders(self, start, end, wordlist):
            """
            :type start: str
            :type end: str
            :type wordlist: Set[str]
            :rtype: List[List[int]]
            """
            # Use BFS as for shortest path
            path = [start]
            queue = collections.deque([(start, path)]) # save path for backtracking
            nextq = collections.deque([])
            self.res = []
            while queue:
                word, path = queue.popleft()
                for i in xrange(len(word)):
                    for y in xrange(ord('a'), ord('z')+1):
                        newWord = word[:i]+chr(y)+word[i+1:]
                        if newWord == word or newWord in path: # only check path for dup
                            continue
                        elif newWord == end:
                            self.res.append(path+[end])
                        elif newWord in wordlist:
                            nextq.append((newWord, path+[newWord]))
                if not queue:
                    if self.res:
                        return self.res # at least found some
                    queue, nextq = nextq, queue
            return []

Log in to reply
 

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