Word Search

Given an m x n board and a word, find if the word exists in the grid.

The word can be constructed from letters of sequentially adjacent cells, where “adjacent” cells are horizontally or vertically neighboring. The same letter cell may not be used more than once.

Example 1:

Input: board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCCED"
Output: true

Example 2:

Input: board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "SEE"
Output: true

Example 3:

Input: board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCB"
Output: false

dfs + backtrack

注意这种回溯的题型里，最好直接修改原数据结构，如果每次都create new memory会很慢，可以用pos variable来记录位置。

Solution：

class Solution(object):
 def exist(self, board, word):
 “””
 :type board: List[List[str]]
 :type word: str
 :rtype: bool
 “””
 # find the first element 
 # dfs 
 # mark current visited
 # dfs next layer with word[1:]
 self.ans = False 
 rowNum = len(board)
 colNum = len(board[0])
 visited = [[0 for _ in range(colNum)] for _ in range(rowNum)]
 direction = [(0, 1), (1,0), (-1, 0), (0, -1)]
 word = list(word)
 def dfs(i, j, newWord, pos):
 if visited[i][j] == 1 or self.ans:
 return 
 visited[i][j] = 1
 if pos == len(newWord)-1:
 self.ans = True
 return
 
 for each in direction:
 x, y = i+each[0], j+each[1]
 if x < 0 or x >= rowNum or y < 0 or y >= colNum or board[x][y] != newWord[pos+1]:
 continue
 dfs(x, y, newWord, pos+1)
 visited[i][j] = 0
 
 
 for i in range(rowNum):
 for j in range(colNum):
 if board[i][j] == word[0]:
 dfs(i,j, word, 0)
 if self.ans == True:
 return self.ans
 return self.ans