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) {
        const int m = board.size(), n = board.front().size();
        if (m * n < word.size()) {
            return false;
        }

        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                if (exist(board, word, 0, i, j)) {
                    return true;
                }
            }
        }

        return false;
    }

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

        const int m = board.size(), n = board.front().size();
        if (0 <= row && row < m && 0 <= column && column < n && board[row][column] == word[index]) {
            char letter = board[row][column];
            board[row][column] = '#';
            bool result = exist(board, word, index + 1, row + 1, column) ||
                exist(board, word, index + 1, row - 1, column) ||
                exist(board, word, index + 1, row, column + 1) ||
                exist(board, word, index + 1, row, column - 1);

            board[row][column] = letter;

            return result;
        } else {
            return false;
        }
    }
};