Word Search [Medium] — DFS Backtracking on Grid

Problem Statement

Given an m×n grid of characters and a word, return true if the word exists in the grid, constructed from sequentially adjacent cells (no cell reused).

board = [["A","B","C","E"],
         ["S","F","C","S"],
         ["A","D","E","E"]]
word = "ABCCED" → true

Intuition

DFS from every cell that matches word[0]. Mark cell visited by temporarily changing it, recurse in 4 directions, then restore.

Solutions

C++

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

Java

public boolean exist(char[][] board, String word) {
    for (int i=0;i<board.length;i++)
        for (int j=0;j<board[0].length;j++)
            if (dfs(board,word,i,j,0)) return true;
    return false;
}
boolean dfs(char[][] b, String w, int i, int j, int k) {
    if (k==w.length()) return true;
    if (i<0||i>=b.length||j<0||j>=b[0].length||b[i][j]!=w.charAt(k)) return false;
    char tmp=b[i][j]; b[i][j]='#';
    boolean f=dfs(b,w,i+1,j,k+1)||dfs(b,w,i-1,j,k+1)||dfs(b,w,i,j+1,k+1)||dfs(b,w,i,j-1,k+1);
    b[i][j]=tmp; return f;
}

JavaScript

var exist = function(board, word) {
    const m=board.length, n=board[0].length;
    function dfs(i,j,k){
        if(k===word.length) return true;
        if(i<0||i>=m||j<0||j>=n||board[i][j]!==word[k]) return false;
        const tmp=board[i][j]; board[i][j]='#';
        const f=dfs(i+1,j,k+1)||dfs(i-1,j,k+1)||dfs(i,j+1,k+1)||dfs(i,j-1,k+1);
        board[i][j]=tmp; return f;
    }
    for(let i=0;i<m;i++) for(let j=0;j<n;j++) if(dfs(i,j,0)) return true;
    return false;
};

Python

def exist(board: list[list[str]], word: str) -> bool:
    m, n = len(board), len(board[0])
    def dfs(i, j, k):
        if k == len(word): return True
        if not (0 <= i < m and 0 <= j < n) or board[i][j] != word[k]: return False
        tmp, board[i][j] = board[i][j], '#'
        found = any(dfs(i+di, j+dj, k+1) for di,dj in [(1,0),(-1,0),(0,1),(0,-1)])
        board[i][j] = tmp
        return found
    return any(dfs(i,j,0) for i in range(m) for j in range(n))

Complexity

Time: O(m×n×4^L) where L = word length
Space: O(L) recursion depth