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

• 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
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()
best = depth
break
elif i in dict:
queue.insert(0, (i, depth + 1))
dict.remove(i)
if i not in graph:
graph[i] = set()
elif i in visited:
if i not in graph:
graph[i] = set()
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:
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)
if i not in graph:
graph[i] = set()
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:]``````

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