Given a 2D board and a word, find if the word exists in the grid.

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

Example:

``````board =
[
['A','B','C','E'],
['S','F','C','S'],
['A','D','E','E']
]

Given word = "ABCCED", return true.
Given word = "SEE", return true.
Given word = "ABCB", return false.
``````

Approach 1: DFS.

### # Code (Python)

Approach 1:

``````    def exist(self, board: 'List[List[str]]', word: 'str') -> 'bool':
width, height = len(board), len(board)
if not width or not height:
return False
for h in range(height):
for w in range(width):
if self._search(w, h, 0, word, board):
return True
return False

def _search(self, w, h, index, word, board):
if index == len(word):
return True
if 0 <= w < len(board) and 0 <= h < len(board) and board[h][w] == word[index]:
# trick to mark as visited (can also have an additional 2d boolean array, or keep a set of coordinates)
board[h][w] = '&'
for delta_w, delta_h in [(1, 0), (0, 1), (-1, 0), (0, -1)]:
if self._search(delta_w + w, delta_h + h, index + 1, word, board):
# recover board state
board[h][w] = word[index]
return True
# recover board state
board[h][w] = word[index]
return False
``````

### # Code (C++)

Approach 1:

``````class Solution {
private:
vector<vector<bool>> visited;
bool exist(vector<vector<char>>& board, int row, int col, string word, int level) {
if (visited[row][col] || board[row][col] != word[level])
return false;
else if (level == word.size() - 1)
return true;
int rowSize = board.size();
int colSize = board.size();
visited[row][col] = true;
if (row + 1 < rowSize && exist(board, row + 1, col, word, level + 1) ||
row - 1 >= 0      && exist(board, row - 1, col, word, level + 1) ||
col + 1 < colSize && exist(board, row, col + 1, word, level + 1) ||
col - 1 >= 0      && exist(board, row, col - 1, word, level + 1))
return true;
visited[row][col] = false;
return false;
}
public:
bool exist(vector<vector<char>>& board, string word) {
int rowSize = board.size();
if (rowSize == 0)
return false;
int colSize = board.size();
if (colSize == 0)
return false;
visited = vector<vector<bool>>(rowSize, vector<bool>(colSize, false));
for (int row = 0; row < rowSize; ++row)
{
for (int col = 0; col < colSize; ++col)
{
if (exist(board, row, col, word, 0))
return true;
}
}
return false;
}
};
``````