Word Search — DFS with Backtracking

Problem

Given an m x n grid of characters and a word, return true if word exists as a sequence of adjacent (4-directional) cells, each used at most once.

Approach — DFS Backtracking

For each cell matching the first letter, DFS tries to extend. Temporarily mark cell as visited by replacing its char, then restore on backtrack.

Time: O(mn4^L) worst | Space: O(L)

Solutions

Python

class Solution:
    def exist(self, board: list[list[str]], word: str) -> bool:
        R,C=len(board),len(board[0])
        def dfs(r,c,i):
            if i==len(word): return True
            if not(0<=r<R and 0<=c<C) or board[r][c]!=word[i]: return False
            tmp,board[r][c]=board[r][c],'#'
            for dr,dc in[(1,0),(-1,0),(0,1),(0,-1)]:
                if dfs(r+dr,c+dc,i+1): board[r][c]=tmp; return True
            board[r][c]=tmp; return False
        return any(dfs(r,c,0) for r in range(R) for c in range(C))

C++

class Solution {
    bool dfs(vector<vector<char>>& b, const string& w, int r, int c, int i){
        if(i==w.size()) return true;
        if(r<0||r>=b.size()||c<0||c>=b[0].size()||b[r][c]!=w[i]) return false;
        char tmp=b[r][c]; b[r][c]='#';
        bool ok=dfs(b,w,r+1,c,i+1)||dfs(b,w,r-1,c,i+1)||dfs(b,w,r,c+1,i+1)||dfs(b,w,r,c-1,i+1);
        b[r][c]=tmp; return ok;
    }
public:
    bool exist(vector<vector<char>>& b, string w){
        for(int r=0;r<b.size();r++) for(int c=0;c<b[0].size();c++)
            if(dfs(b,w,r,c,0)) return true;
        return false;
    }
};

Java

class Solution {
    private boolean dfs(char[][] b, String w, int r, int c, int i){
        if(i==w.length()) return true;
        if(r<0||r>=b.length||c<0||c>=b[0].length||b[r][c]!=w.charAt(i)) return false;
        char tmp=b[r][c]; b[r][c]='#';
        boolean ok=dfs(b,w,r+1,c,i+1)||dfs(b,w,r-1,c,i+1)||dfs(b,w,r,c+1,i+1)||dfs(b,w,r,c-1,i+1);
        b[r][c]=tmp; return ok;
    }
    public boolean exist(char[][] b, String w){
        for(int r=0;r<b.length;r++) for(int c=0;c<b[0].length;c++)
            if(dfs(b,w,r,c,0)) return true;
        return false;
    }
}

Complexity

Time: O(mn4^L) | Space: O(L)