# Python simple dfs solution

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

def exist_helper(self, board, word, i, j):
if board[i][j] == word[0]:
if not word[1:]:
return True
board[i][j] = " " # indicate used cell
if i > 0 and self.exist_helper(board, word[1:], i-1, j):
return True
if i < len(board)-1 and self.exist_helper(board, word[1:], i+1, j):
return True
if j > 0 and self.exist_helper(board, word[1:], i, j-1):
return True
if j < len(board[0])-1 and self.exist_helper(board, word[1:], i, j+1):
return True
board[i][j] = word[0] # update the cell to its original value
return False
else:
return False``````

• what would be time complexity for this algorithm? exist has loop of O(rows * cols) and exist_helper, checks like DFS which seems like len of word. But in all 4 direction.

• @dharaB

Should it be O(mn4^len(word))?

• This post is deleted!

• This post is deleted!

• The above code is quite good but some cases add a bit of confusion.
Like:

``````if not word[1:]:
return True
``````

and extra `else` at the end.

The code can be simplified to:

``````def search_word_util(self, board, row, col, word):
if len(word) == 0:
return True

if row < 0 or row >= len(board) or col < 0 or col >= len(board[0]) or board[row][col] != word[0]:
return False

board[row][col] = " "

if self.search_word_util(board, row-1, col, word[1:]):
return True
if self.search_word_util(board, row+1, col, word[1:]):
return True
if self.search_word_util(board, row, col-1, word[1:]):
return True
if self.search_word_util(board, row, col+1, word[1:]):
return True

board[row][col] = word[0]
return False
``````

It handles all the cases for which extra conditions were added in the above code.

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