Word Search Problems — Trie + Backtracking Patterns

def exist(board, word):
    rows, cols = len(board), len(board[0])

    def dfs(r, c, k):
        if k == len(word): return True
        if r<0 or r>=rows or c<0 or c>=cols or board[r][c]!=word[k]:
            return False
        temp = board[r][c]
        board[r][c] = '#'
        found = any(dfs(r+dr,c+dc,k+1) for dr,dc in [(-1,0),(1,0),(0,-1),(0,1)])
        board[r][c] = temp
        return found

    return any(dfs(r,c,0) for r in range(rows) for c in range(cols))

class TrieNode:
    def __init__(self):
        self.children = {}
        self.word = None

def findWords(board, words):
    root = TrieNode()
    for w in words:
        node = root
        for c in w:
            if c not in node.children:
                node.children[c] = TrieNode()
            node = node.children[c]
        node.word = w

    rows, cols = len(board), len(board[0])
    res = []

    def dfs(r, c, node):
        ch = board[r][c]
        if ch not in node.children: return
        next_node = node.children[ch]
        if next_node.word:
            res.append(next_node.word)
            next_node.word = None
        board[r][c] = '#'
        for dr,dc in [(-1,0),(1,0),(0,-1),(0,1)]:
            nr,nc = r+dr,c+dc
            if 0<=nr<rows and 0<=nc<cols and board[nr][nc]!='#':
                dfs(nr,nc,next_node)
        board[r][c] = ch
        if not next_node.children:
            del node.children[ch]

    for r in range(rows):
        for c in range(cols):
            dfs(r,c,root)
    return res

function exist(board,word){
    const R=board.length,C=board[0].length;
    const dfs=(r,c,k)=>{
        if(k===word.length)return true;
        if(r<0||r>=R||c<0||c>=C||board[r][c]!==word[k])return false;
        const tmp=board[r][c]; board[r][c]='#';
        const found=[[-1,0],[1,0],[0,-1],[0,1]].some(([dr,dc])=>dfs(r+dr,c+dc,k+1));
        board[r][c]=tmp; return found;
    };
    for(let r=0;r<R;r++)for(let c=0;c<C;c++)if(dfs(r,c,0))return true;
    return false;
}

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

bool dfs(vector<vector<char>>&b,string&w,int r,int c,int k){
    if(k==(int)w.size())return true;
    if(r<0||r>=(int)b.size()||c<0||c>=(int)b[0].size()||b[r][c]!=w[k])return false;
    char tmp=b[r][c];b[r][c]='#';
    bool f=dfs(b,w,r-1,c,k+1)||dfs(b,w,r+1,c,k+1)||dfs(b,w,r,c-1,k+1)||dfs(b,w,r,c+1,k+1);
    b[r][c]=tmp;return f;
}

/* C: same DFS with char replacement, 2D grid dimensions passed as params */