79. Word Search

2020, Dec 05 2 mins read

1. Description

Given an m x n grid of characters board and a string word, return true if 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.

2. Example

Example 1

Example 1
Input: board = [[“A”,“B”,“C”,“E”],[“S”,“F”,“C”,“S”],[“A”,“D”,“E”,“E”]], word = “ABCCED”
Output: true

Example 2

Example 2
Input: board = [[“A”,“B”,“C”,“E”],[“S”,“F”,“C”,“S”],[“A”,“D”,“E”,“E”]], word = “SEE”
Output: true

Example 3

Example 3
Input: board = [[“A”,“B”,“C”,“E”],[“S”,“F”,“C”,“S”],[“A”,“D”,“E”,“E”]], word = “ABCB”
Output: false

3. Constraints

m == board.length
n = board[i].length
1 <= m, n <= 6
1 <= word.length <= 15
board and word consists of only lowercase and uppercase English letters.

4. Solutions

Backtracking

n is the number of letters in the board, l = word.size()
Time complexity: O($n3^l$)
Space complexity: O(l)

class Solution {
public:
    bool exist(vector<vector<char>> board, const string &word) {
        m = board.size(), n = board.front().size();
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                if (board[i][j] == word.front()) {
                    bool find = find_word(board, word, i, j, 0);
                    if (find) {
                        return true;
                    }
                }
            }
        }

        return false;
    }

private:
    int m = 0, n = 0;

    bool find_word(
        vector<vector<char>> &board,
        const string &word,
        int row,
        int column,
        int index) {
        if (index == word.size()) {
            return true;
        }

        if (0 <= row && row < m && 0 <= column && column < n && board[row][column] == word[index]) {
            char backup = board[row][column];
            board[row][column] = '#';

            bool found = find_word(board, word, row + 1, column, index + 1) ||
                find_word(board, word, row - 1, column, index + 1) ||
                find_word(board, word, row, column + 1, index + 1) ||
                find_word(board, word, row, column - 1, index + 1);

            board[row][column] = backup;

            return found;
        }

        return false;
    }
};