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.

# Solution

Approach 1: DFS.

# Code (Python)

Approach 1:

    def exist(self, board: 'List[List[str]]', word: 'str') -> 'bool':
        width, height = len(board[0]), 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[0]) 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[0].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[0].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;
    }
};