# TLE in python by using BFS and DFS. Anyone can help to improve the performance?

• It seems BFS takes a long time which causes the TLE. Anyone can help to improve the performance?
I ran those test cases which TLE locally and they passed. So at least the algorithm is correct, except it takes more time.

``````def distance(src, des):
if src is None or des is None:
return -1
dis = 0
for i in range(len(src)):
if not src[i] == des[i]:
dis += 1
return dis

def bfs(wordSet, node, endWord):
queue = [node, None]
temp = set()
while len(queue) > 0:
current = queue.pop()
if current is None:
for t in temp:
wordSet.remove(t)
temp = set()
if len(queue) > 0:
queue.insert(0, None)
else:
if distance(current[0], endWord) == 1:
current[1].append((endWord, []))
else:
for i in range(len(current[0])):
for ch in string.ascii_lowercase:
if not ch == current[0][i]:
word = current[0][0:i] + ch +current[0][i + 1:]
if word in wordSet:
nextNode = (word, [])
queue.insert(0, nextNode)
current[1].append(nextNode)
temp.add(word)

def dfs(node, curList, res, endWord):
if node[0] == endWord:
temp = list(curList)
res.append(temp)
else:
for kid in node[1]:
curList.append(kid[0])
dfs(kid, curList, res, endWord)
curList.pop()

class Solution(object):
def findLadders(self, beginWord, endWord, wordList):
"""
:type beginWord: str
:type endWord: str
:type wordList: List[str]
:rtype: List[List[str]]
BFS DFS with cal string distance
"""
exist = False
for word in wordList:
if word == endWord:
exist = True
break
for i in range(len(wordList)):
if wordList[i] == beginWord:
wordList[i] = None
break
result = []
if exist:
root = (beginWord, [])
bfs(set(wordList), root, endWord)
dfs(root, [beginWord], result, endWord)
return result
``````

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