Word Search

MediumBacktracking

Given a grid of letters and a word, return true if the word can be formed from sequentially adjacent cells, without reusing a cell.

Open problem

Constraints

1 <= m, n <= 6
1 <= word.length <= 15

DFS backtracking from each cell

Time O(m * n * 4^L)Space O(L) recursion depth

From every cell, try to match the word letter by letter moving to adjacent cells. Mark visited cells temporarily to prevent reuse and restore them when backtracking.

#include <bits/stdc++.h>
using namespace std;

bool exist(vector<vector<char>>& board, string word) {
    int m = board.size(), n = board[0].size();
    function<bool(int,int,int)> dfs = [&](int r, int c, int k) -> bool {
        if (k == (int)word.size()) return true;
        if (r < 0 || c < 0 || r >= m || c >= n || board[r][c] != word[k]) return false;
        char tmp = board[r][c];
        board[r][c] = '#';
        bool found = dfs(r+1,c,k+1) || dfs(r-1,c,k+1) || dfs(r,c+1,k+1) || dfs(r,c-1,k+1);
        board[r][c] = tmp;
        return found;
    };
    for (int i = 0; i < m; i++)
        for (int j = 0; j < n; j++)
            if (dfs(i, j, 0)) return true;
    return false;
}