# Python DFS TLE, Help!

• ``````class Solution:
# @param board, a list of lists of 1 length string
# @param word, a string
# @return a boolean
def exist(self, board, word):
X = len(board)
Y = len(board[0])
cor_add = lambda x, y: (x[0]+y[0], x[1]+y[1])
neighbor = [(1,0), (-1,0), (0,1), (0,-1)]
stack = []
for i in xrange(X):
for j in xrange(Y):
if board[i][j] == word[0]:
stack.append(([(i, j)], word[1:]))
while not stack == []:
s = stack.pop()
c, w = s
if w == '':
return True
l = c[-1]
ln = [cor_add(l, n) for n in neighbor]
for x in ln:
if not (x[0]>=0 and x[0]<X and x[1]>=0 and x[1]<Y):
continue
if not (board[x[0]][x[1]] == w[0]):
continue
if x not in c:
stack.append((c + [x], w[1:]))
return False
``````

I ran test cases of:
==== 1, 2, 3

examples given in the problem

==== 4

["aaaaaaaaaaaaaaaaaaaaaaaa...aaaaaaaaaaab"]

"baaaaaaaaaaaaaaaaaa...

==== 5

["elxllvxegzmvgnhrypvagxrgwktiqnyuavfnsfsbgewnrferubrcykjwveenrfhtamhvtzwafspzxvqtwkxwwgttkzgdenzhcgcvhyxosonrjgmhsjeo", ...
"oajgdkcokvfpdaslnmomrpgwitwdoku"

On my MBP:

\$ time python word-search.py

True

True

False

True

True

``````     11514 function calls in 0.087 seconds
``````

Ordered by: standard name

ncalls tottime percall cumtime percall filename:lineno(function)

``````    1    0.000    0.000    0.087    0.087 <string>:1(<module>)
1    0.001    0.001    0.087    0.087 word-search.py:31(main)
5    0.079    0.016    0.086    0.017 word-search.py:5(exist)
6988    0.006    0.000    0.006    0.000 word-search.py:8(<lambda>)
10    0.000    0.000    0.000    0.000 {len}
2757    0.000    0.000    0.000    0.000 {method 'append' of 'list' objects}
1    0.000    0.000    0.000    0.000 {method 'disable' of '_lsprof.Profiler' objects}
1751    0.000    0.000    0.000    0.000 {method 'pop' of 'list' objects}
``````

real 0m0.116s

user 0m0.101s

sys 0m0.013s

I don't know how much the time limit is, but I think you need to give python at least 100ms per test case.

• Hi, there.
It is very obvious that this problem should be done with some backtracking or recursion. Although your code is not using recursion explicitly, you are using stack to memorize the previous states.

I think the most important message of this problem is to teach us how to break the recursive loop in some condition to avoid the unnecessary checking, so that we do not need to search the whole dfs tree.

More specifically, we do not need to generate all the neighbors for each position meets the requirement here. If there are multiple characters in the board same with desired one and say, if we can find the word going through the first one, why do we bother to keep the rest in the stack and check them?

Here is the code which explains the idea avoiding redundant searching and checking.

``````class Solution:
# @param {character[][]} board
# @param {string} word
# @return {boolean}
def _exist(self, board, word, i, j):
if board[i][j] == word[0]:
if not word[1:]:
return True
board[i][j] = " "
if 0 < i and self._exist(board, word[1:], i-1, j):
return True
if i < len(board)-1 and self._exist(board, word[1:], i+1, j):
return True
if 0 < j and self._exist(board, word[1:], i, j-1):
return True
if j < len(board[0])-1 and self._exist(board, word[1:], i, j+1):
return True
board[i][j] = word[0]
return False
return False

def exist(self, board, word):
if len(word) > len(board) * len(board[0]):
return False
for i in range(len(board)):
for j in range(len(board[0])):
if self._exist(board, word, i, j):
return True
return False
``````

It takes 3ms for the following case, while your code takes around 100ms. With more testcases it will cause TLE. Hope this can help.

board = ["aaaaaaaaaaaaaaaaaaaaaaaaaaaaaa","aaaaaaaaaaaaaaaaaaaaaaaaaaaaaa","aaaaaaaaaaaaaaaaaaaaaaaaaaaaaa","aaaaaaaaaaaaaaaaaaaaaaaaaaaaaa","aaaaaaaaaaaaaaaaaaaaaaaaaaaaaa","aaaaaaaaaaaaaaaaaaaaaaaaaaaaaa","aaaaaaaaaaaaaaaaaaaaaaaaaaaaaa","aaaaaaaaaaaaaaaaaaaaaaaaaaaaaa","aaaaaaaaaaaaaaaaaaaaaaaaaaaaaa","aaaaaaaaaaaaaaaaaaaaaaaaaaaaaa","aaaaaaaaaaaaaaaaaaaaaaaaaaaaaa","aaaaaaaaaaaaaaaaaaaaaaaaaaaaaa","aaaaaaaaaaaaaaaaaaaaaaaaaaaaaa","aaaaaaaaaaaaaaaaaaaaaaaaaaaaaa","aaaaaaaaaaaaaaaaaaaaaaaaaaaaaa","aaaaaaaaaaaaaaaaaaaaaaaaaaaaaa","aaaaaaaaaaaaaaaaaaaaaaaaaaaaaa","aaaaaaaaaaaaaaaaaaaaaaaaaaaaaa","aaaaaaaaaaaaaaaaaaaaaaaaaaaaaa","aaaaaaaaaaaaaaaaaaaaaaaaaaaaaa","aaaaaaaaaaaaaaaaaaaaaaaaaaaaaa","aaaaaaaaaaaaaaaaaaaaaaaaaaaaaa","aaaaaaaaaaaaaaaaaaaaaaaaaaaaaa","aaaaaaaaaaaaaaaaaaaaaaaaaaaaaa","aaaaaaaaaaaaaaaaaaaaaaaaaaaaaa","aaaaaaaaaaaaaaaaaaaaaaaaaaaaaa","aaaaaaaaaaaaaaaaaaaaaaaaaaaaaa","aaaaaaaaaaaaaaaaaaaaaaaaaaaaaa","aaaaaaaaaaaaaaaaaaaaaaaaaaaaaa","aaaaaaaaaaaaaaaaaaaaaaaaaaaaab"]

word =
"baaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa"

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