# 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

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`