[Python]AC code is much slower than TLE code (12s > 0.3s) on my computer. Any idea?


  • 0
    X

    The code is ugly. Basicly it is bfs build a graph then dfs find path. These two solutions are very similar. The first solution got accepted somehow. But it actually took longer than solution 2 (which won't put duplicated edge into bfs queue) on my computer. Solution2 got TLE on ("nape", "mild").

    Any idea will be highly appreciated. Thank you!

    Solution1

    class Solution:
    # @param start, a string
    # @param end, a string
    # @param dict, a set of string
    # @return a list of lists of string
    def findLadders(self, start, end, dict):
        queue, ld, visited = [(start, 0)], 0, set()
        best = None
        graph = {}
        while queue:
            node, depth = queue.pop()
            if depth > ld:
                if best is not None:
                    break
                visited = set()
            for i in self.changes(node):
                if i == end:
                    if i not in graph:
                        graph[i] = set()
                    graph[i].add(node)
                    best = depth
                    break
                elif i in dict:
                    queue.insert(0, (i, depth + 1))
                    visited.add(i)
                    dict.remove(i)
                    if i not in graph:
                        graph[i] = set()
                    graph[i].add(node)
                elif i in visited:
                    if i not in graph:
                        graph[i] = set()
                    graph[i].add(node)
            ld = depth
        return self.dfs(graph, start, end)
    
    def dfs(self, graph, start, end):
        res = []
        stack = [(end, [end])]
        while stack:
            node, path = stack.pop()
            if node == start:
                res.append(path[::-1])
                continue
            if node not in graph:
                continue
            for i in graph[node]:
                stack.append((i, path+[i]))
        return res
    
    
    chars = [chr(i) for i in xrange(97, 123)]
    def changes(self, word):
        for i in xrange(len(word)):
            for j in self.chars:
                if j != word[i]:
                    yield word[:i] + j + word[i+1:]
    

    Solution2

    class Solution:
    def findLadders(self, start, end, dict):
        if type(dict) == list:
            dict = set(dict)
        return self.findPath(self.buildGraph(start, end, dict), start, end)
    
    def buildGraph(self, start, end, dict):
        """
        bfs by layer, build a graph for transform path
        """
        graph, queue, visited = {}, [start], set()
        best, level, cLevel, nLevel = None, 0, 1, 0
        while queue:
            node = queue.pop(0)
            for i in self.changes(node):
                if i in dict:
                    if i in graph and node in graph[i]:
                        continue
                    # into the queue
                    nLevel += 1
                    queue.append(i)
                    visited.add(i)
                    if i not in graph:
                        graph[i] = set()
                    graph[i].add(node)
                if i == end:
                    # ends
                    best = level
                    break
            cLevel -= 1
            if cLevel == 0:
                if best is not None:
                    break
                level += 1
                cLevel = nLevel
                nLevel = 0
                dict -= visited
                visited.clear()
        return graph
    
    def findPath(self, graph, start, end):
        """
        find the path from end to start, output reverse
        """
        res = []
        stack = [(end, [end])]
        while stack:
            node, path = stack.pop()
            if node == start:
                res.append(path[::-1])
                continue
            if node not in graph:
                continue
            for i in graph[node]:
                stack.append((i, path+[i]))
        return res
    
    chars = [chr(i) for i in xrange(97, 123)]
    def changes(self, word):
        """
        helper function, yield changes of a word
        """
        for i in xrange(len(word)):
            for j in self.chars:
                if j != word[i]:
                    yield word[:i] + j + word[i+1:]

Log in to reply
 

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