# Strange Python TLE problem?

• 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

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.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
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``````

• 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.

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

• 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.

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

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