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, i1, j, word[1:]) \
or self.dfs(board, i, j+1, word[1:]) or self.dfs(board, i, j1, word[1:])
board[i][j] = tmp
return res
Python dfs solution with comments.


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 = (i1>=0 and DFS(i1, j, l+1)) or (i+1 < M and DFS(i+1, j, l+1)) or\ (j1 >= 0 and DFS(i, j1, 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


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.visitedSet.add((row,col)) self.dfs(board,row+1,col,i+1) self.dfs(board,row1,col,i+1) self.dfs(board,row,col+1,i+1) self.dfs(board,row,col1,i+1) if not self.found: self.visitedSet.remove(self.visited.pop())

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, i1, j, word[1:], visited) or self.dfs(board, i+1, j, word[1:], visited) \ or self.dfs(board, i, j1, word[1:], visited) or self.dfs(board, i, j+1, word[1:], visited) if not res: a = visited.pop() return res


@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 OrderedSet.