Time Limit Exceed on my python solution

• Hi there, I am trying to use Python to solve the problem. I use the DFS method but got a TLE. I have seen other solutions using C++ or Java. But I think the basic idea of those Accepted codes are just the same with mine. So any suggestions on my code? I will very appreciate your suggestions!

``````class Solution:
# @param board, a list of lists of 1 length string
# @param word, a string
# @return a boolean
def exist(self, board, word):
for i in range(0, len(board)):
s = board[i]
for j in range(0, len(s)):
if board[i][j] == word[0]:
visited = [[False for m in range(len(board[0]))] for n in range(len(board))]
if DFS(board, word, visited, 0, i, j):
return True
return False
def DFS(board, word, visited, index, i, j):
if i >= 0 and j >=0 and i < len(board) and j < len(board[0]) \
and board[i][j] == word[index] and visited[i][j] == False:
visited[i][j] = True
if index + 1 == len(word):
return True
if DFS(board, word, visited, index + 1, i + 1, j):
return True
elif DFS(board, word, visited, index + 1, i - 1, j):
return True
elif DFS(board, word, visited, index + 1, i , j + 1):
return True
elif DFS(board, word, visited, index + 1, i , j - 1):
return True
return False``````

• In fact I think your code is much conciser than my java version (Maybe it is just due to the different languages). So I corrected all your errors.

``````class Solution:
# @param board, a list of lists of 1 length string
# @param word, a string
# @return a boolean
def exist(self, board, word):
visited = [[False for m in range(len(board[0]))] for n in range(len(board))] #Key improvement
for i in range(0,len(board)):
for j in range(0,len(board[0])):
if board[i][j] == word[0]:
if self.DFS(board, word, visited, 0, i, j):
return True
return False

def DFS(self,board, word, visited, index, i, j):# Why do you have no self in your code?
if i >= 0 and j >=0 and i < len(board) and j < len(board[0]) \
and board[i][j] == word[index] and visited[i][j] == False:
visited[i][j] = True
if index + 1 == len(word):
return True
if self.DFS(board, word, visited, index + 1, i + 1, j):
return True
if self.DFS(board, word, visited, index + 1, i - 1, j):
return True
if self.DFS(board, word, visited, index + 1, i , j + 1):
return True
if self.DFS(board, word, visited, index + 1, i , j - 1):
return True
visited[i][j]=False #Key improvement
return False``````

• Hi reeclapple, thank you very much for your answer. I think I find the reason why I got a TLE on my previous code. in my exist function I had to initialise the visited array every time before the search. But in your way, it's faster without initialising the visited very often.

• Also you have to unlabel a point if all of its four direction return false;

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