Word Search

Problem

Given a 2-D grid of characters board and a string word, return true if the word is present in the grid, otherwise return false.

For the word to be present it must be possible to form it with a path in the board with horizontally or vertically neighboring cells. The same cell may not be used more than once in a word.

Examples

Example 1:

Input: 
board = [
  ["A","B","C","D"],
  ["S","A","A","T"],
  ["A","C","A","E"]
],
word = "CAT"

Example 2:

Input: 
board = [
  ["A","B","C","D"],
  ["S","A","A","T"],
  ["A","C","A","E"]
],
word = "BAT"

Output: false

Constraints

• 1 <= board.length, board[i].length <= 5
• 1 <= word.length <= 10
• board and word consists of only lowercase and uppercase English letters.

You should aim for a solution with O(m * (4^n)) time and O(n) space, where m is the number of cells in the given board and n is the size of the given word.

Solution

Loop over each starting cell. For each cell, perform a DFS, while tracking the path cells.

class Solution {
public:
    bool exist(vector<vector<char>>& board, const string &word) {
        const auto ROWS = board.size();
        const auto COLS = board[0].size();
 
        std::unordered_set<int> path_indices;
        std::function<bool(int, int, int)> runner;
 
        runner = [&](int r, int c, int w_idx) -> bool {
            // If (r,c) invalid index
            if (r < 0 || c < 0 || r >= ROWS || c >= COLS) {
                return false; 
            }
            // If our path is too long, quit
            if (w_idx >= word.size()) {
                return false;
            }
            
            // If this is a index already in the path, quit
            auto flat_idx = r * COLS + c;
            if (path_indices.contains(flat_idx)) {
                return false;
            }
 
            // If (r,c) does not contain word[w_idx], quit
            // Otherwise, check if we found the last char in the word
            if (board[r][c] != word[w_idx]) {
                return false;
            } else if (w_idx == word.size() - 1) {
                return true;
            }
 
            // We have a partial match
            // Check the next word character in all directions
            path_indices.insert(flat_idx);
            if (runner(r - 1, c, w_idx + 1)) { return true; }
            if (runner(r + 1, c, w_idx + 1)) { return true; }
            if (runner(r, c - 1, w_idx + 1)) { return true; }
            if (runner(r, c + 1, w_idx + 1)) { return true; }
            path_indices.erase(flat_idx);
            return false;
        };
 
        // Loop over starting positions
        for (int i = 0; i < ROWS; ++i) {
            for (int j = 0; j < COLS; ++j) {
                if (board[i][j] != word[0]) {
                    continue;
                }
                // Found the start of the word at (i,j)
                // Perform a walk
                if (runner(i, j, 0)) {
                    return true;
                }
            }
        }
        return false;
    }
};