TLE in python by using BFS and DFS. Anyone can help to improve the performance?


  • 0
    R

    It seems BFS takes a long time which causes the TLE. Anyone can help to improve the performance?
    I ran those test cases which TLE locally and they passed. So at least the algorithm is correct, except it takes more time.

    def distance(src, des):
        if src is None or des is None:
            return -1
        dis = 0
        for i in range(len(src)):
            if not src[i] == des[i]:
                dis += 1
        return dis
    
    
    def bfs(wordSet, node, endWord):
        queue = [node, None]
        temp = set()
        while len(queue) > 0:
            current = queue.pop()
            if current is None:
                for t in temp:
                    wordSet.remove(t)
                temp = set()
                if len(queue) > 0:
                    queue.insert(0, None)
            else:
                if distance(current[0], endWord) == 1:
                    current[1].append((endWord, []))
                else:
                    for i in range(len(current[0])):
                        for ch in string.ascii_lowercase:
                            if not ch == current[0][i]:
                                word = current[0][0:i] + ch +current[0][i + 1:]
                                if word in wordSet:
                                    nextNode = (word, [])
                                    queue.insert(0, nextNode)
                                    current[1].append(nextNode)
                                    temp.add(word)
    
    def dfs(node, curList, res, endWord):
        if node[0] == endWord:
            temp = list(curList)
            res.append(temp)
        else:
            for kid in node[1]:
                curList.append(kid[0])
                dfs(kid, curList, res, endWord)
                curList.pop()
    
    
    class Solution(object):
        def findLadders(self, beginWord, endWord, wordList):
            """
            :type beginWord: str
            :type endWord: str
            :type wordList: List[str]
            :rtype: List[List[str]]
            BFS DFS with cal string distance
            """
            exist = False
            for word in wordList:
                if word == endWord:
                    exist = True
                    break
            for i in range(len(wordList)):
                if wordList[i] == beginWord:
                    wordList[i] = None
                    break
            result = []
            if exist:
                root = (beginWord, [])
                bfs(set(wordList), root, endWord)
                dfs(root, [beginWord], result, endWord)
            return result
    

Log in to reply
 

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