# 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