Strange Python TLE problem?


  • 0
    W

    For 'nape','mild' input, my Python code returns a solution in a few milliseconds on my computer, but I get TLE with OJ.
    Anyone knows what is happening?
    I have included my code below.

    I'm using BFS with a simple heuristic function h to guide the search.
    I also use a hash table tt to store information about the words visited.
    The solution paths are reconstructed at the end using parents stored in the hash table.

    class Solution:
    # @param start, a string
    # @param end, a string
    # @param dict, a set of string
    # @return a list of lists of string
    
    # a simple heuristic function h to guide the search.
    # returns the number of chars different from the end word 
    def h(self, start, end):
        cost=0
        for i in range(len(start)):
            if start[i]!=end[i]: cost = cost+1
        return cost    
    
    # information about each visited word
    class State:
        def __init__(self,g,h,parents):
            self.g=g  # min distance from the start
            self.h=h  # min distance to the end
            self.parents=parents  # parents on the paths. Used to reconstruct solution paths
            
    # reconstruct solution paths at the end
    def solutionPaths(self,word):
        parents=self.tt[word].parents
        if len(parents)==0: return [[word]]
        allPaths=[]
        for parent in parents:
            paths=self.solutionPaths(parent)
            for path in paths:
                path.append(word)
            allPaths.extend(paths)
        return allPaths
    
    def findLadders(self, start, end, dict):
        self.MAX_DIST=100
        self.chars = 'abcdefghijklmnopqrstuvwxyz'
    
        self.leavesAtLevel=[set() for i in range(self.MAX_DIST)] # initial leaves for BFS
        self.tt={} # hash table stores information for each visited word
        
        # add the start to leaves and cache
        h=self.h(start,end)
        self.leavesAtLevel[h].add(start)
        self.tt[start]=self.State(0,h,set())
        
        # BFS on each level
        for level in range(h,self.MAX_DIST):
            leaves=self.leavesAtLevel[level]
            if len(leaves)==0: continue
            minDist=self.MAX_DIST
            for word in leaves:
                state = self.tt[word]
                dist = self.search(word,end,dict,state.g,level-state.g,state.parents)
                if dist<minDist: minDist=dist
            if end in self.tt: break  # solution found
            if minDist >= self.MAX_DIST: return[]  # no solution exist
        return self.solutionPaths(end)
    
    # only consider words with cost no more than bound. Put the other words in leaves  
    def search(self,start,end,dict,dist,bound,parents):
        if start in self.tt:
            cost=self.tt[start].h
            if self.tt[start].g<dist: return cost #already visited and closer to the source
            elif self.tt[start].g==dist: #another path to add
                self.tt[start]=self.State(dist,cost,self.tt[start].parents|parents)
            else: #self.tt[start].g>dist: shorter path found. overwrite earlier entry  
                self.tt[start]=self.State(dist,cost,parents) 
        else:
            cost=self.h(start,end)
            self.tt[start]=self.State(dist,cost,parents)
    
        if cost> bound: # is a leaf
            self.leavesAtLevel[cost+dist].add(start)
            return cost
        
        # go through each possible move
        cost=self.MAX_DIST
        for i in range(len(start)):
                for j in range(26):
                    nextWord = start[0:i]+self.chars[j]+start[i+1:];
                    if nextWord in dict and start[i]!=self.chars[j]:
                        c=1+self.search(nextWord,end,dict,dist+1,bound-1,{start})
                        if c<cost: cost=c
                
        self.tt[start].h=cost
        return cost

  • 0
    S

    LeetCode runs all test case in once. Sometime, the last test case is incorrect for Time Limit Exceed error. It is better to share algorithm to check it out. Maybe the reason is method is not good enough.


  • 0
    W

    Thanks for the reply. I have modified my oritinal post to includ my code


  • 0
    W

    Actually, I just got it accepted by making the heuristic function simply returns 0. This makes it just a standard BFS without the heuristic search component, and seems to make it slightly faster for this problem, and allows it to be accepted.
    Thanks.


  • 0
    D

    O(N^2logN) algorithm get TLE in Python,(=@__@=) .
    maybe because I use string as the index of dict.


Log in to reply
 

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