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