# Python dfs solution with comments.

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

# check whether can find word, start at (i,j) position
def dfs(self, board, i, j, word):
if len(word) == 0: # all the characters are checked
return True
if i<0 or i>=len(board) or j<0 or j>=len(board[0]) or word[0]!=board[i][j]:
return False
tmp = board[i][j]  # first character is found, check the remaining part
board[i][j] = "#"  # avoid visit agian
# check whether can find "word" along one direction
res = self.dfs(board, i+1, j, word[1:]) or self.dfs(board, i-1, j, word[1:]) \
or self.dfs(board, i, j+1, word[1:]) or self.dfs(board, i, j-1, word[1:])
board[i][j] = tmp
return res``````

• is it correct?

`board[i][j] = "#" # avoid visit agian`

str is immutable, I think we could not replace a character. can we? or I may be wrong.

• Here board is a two dimensional array ，not a list of string～

• Oh... yes, you're right! thanks

• Yes，but we did not change characters inside the string，we replace the string (reassignment)，so it works.

• Similar idea with inner function:

``````def exist(self, board, word):
L= len(word)
# if not L: return True
M = len(board)
# if not M: return False
N = len(board[0])
def DFS(i, j, l):
if board[i][j] != word[l]: return False
if l+1 == L: return True
board[i][j] += '@'
hasFound = (i-1>=0 and DFS(i-1, j, l+1)) or (i+1 < M and DFS(i+1, j, l+1)) or\
(j-1 >= 0 and DFS(i, j-1, l+1)) or (j+1 < N and DFS(i, j+1, l+1))
board[i][j] = board[i][j][0] #backtrace
return hasFound

for i in range(M):
for j in range(N):
if DFS(i,j, 0):
return True
return False``````

• This post is deleted!

• @caikehe Excellent idea ! I want to know the time complexity of DFS ,thank you !~

• without modifying the original board, using a stack to track the path:

``````class Solution(object):
def exist(self, board, word):

self.word = word
self.found = False
for row in range(len(board)):
for col in range(len(board[0])):
self.visited = []
self.visitedSet = set()
self.dfs(board,row,col,0)
if self.found:
return True
return False

def dfs(self,board,row,col,i):

if i == len(self.word):
self.found = True

if not self.found and row >= 0 and col >= 0 and row<len(board) and col<len(board[0]) and board[row][col] == self.word[i] and (row,col) not in self.visitedSet:
self.visited += [(row,col)]
self.dfs(board,row+1,col,i+1)
self.dfs(board,row-1,col,i+1)
self.dfs(board,row,col+1,i+1)
self.dfs(board,row,col-1,i+1)

if not self.found:
self.visitedSet.remove(self.visited.pop())
``````

• @axelramar9

Using a list as stack is enough, no need to use a set:

``````class Solution(object):
def exist(self, board, word):
"""
:type board: List[List[str]]
:type word: str
:rtype: bool
"""
if not board:
return False
for i in range(len(board)):
for j in range(len(board[0])):
if self.dfs(board, i, j, word, []):
return True
return False

# check whether can find word, start at (i,j) position
def dfs(self, board, i, j, word, visited):
if len(word) == 0: # all the characters are checked
return True
if i<0 or i>=len(board) or j<0 or j>=len(board[0]) or word[0]!=board[i][j] or (i, j) in visited:
return False
visited.append((i, j))
res = self.dfs(board, i-1, j, word[1:], visited) or self.dfs(board, i+1, j, word[1:], visited) \
or self.dfs(board, i, j-1, word[1:], visited) or self.dfs(board, i, j+1, word[1:], visited)
if not res:
a = visited.pop()
return res``````

• @WeiFoo yeah, I think that's why we do `board[i][j] = tmp` for other runs of recursion

• @ahoosh a list as a stack is enough, but a set will address the elements in constant time.

Probably (asking all the experts here) a better implementation would be by using OrderedDict.

• So what is the time complexity of this DFS recursion?

• Why using board[0] instead of board[i]?
Or in this case, board[0] length equals board[1] length

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