Word Search I & II: DFS Backtracking on Grid

def exist(board, word):
    rows, cols = len(board), len(board[0])
    def dfs(r, c, idx):
        if idx == len(word): return True
        if r < 0 or r >= rows or c < 0 or c >= cols: return False
        if board[r][c] != word[idx]: return False
        # Mark visited
        temp = board[r][c]
        board[r][c] = '#'
        found = (dfs(r+1,c,idx+1) or dfs(r-1,c,idx+1) or
                 dfs(r,c+1,idx+1) or dfs(r,c-1,idx+1))
        board[r][c] = temp  # restore
        return found

    for r in range(rows):
        for c in range(cols):
            if dfs(r, c, 0): return True
    return False

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

def findWords(board, words):
    # Build trie
    root = TrieNode()
    for w in words:
        node = root
        for ch in w:
            node = node.children.setdefault(ch, TrieNode())
        node.word = w

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

    def dfs(r, c, node):
        if r < 0 or r >= rows or c < 0 or c >= cols: return
        ch = board[r][c]
        if ch == '#' or ch not in node.children: return
        next_node = node.children[ch]
        if next_node.word:
            result.append(next_node.word)
            next_node.word = None  # avoid duplicates
        board[r][c] = '#'
        for dr, dc in [(0,1),(0,-1),(1,0),(-1,0)]:
            dfs(r+dr, c+dc, next_node)
        board[r][c] = ch
        # Prune: remove leaf nodes from trie
        if not next_node.children and not next_node.word:
            del node.children[ch]

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

#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 idx) -> bool {
        if (idx == (int)word.size()) return true;
        if (r<0||r>=m||c<0||c>=n||board[r][c]!=word[idx]) return false;
        char tmp = board[r][c]; board[r][c] = '#';
        bool found = dfs(r+1,c,idx+1)||dfs(r-1,c,idx+1)||
                     dfs(r,c+1,idx+1)||dfs(r,c-1,idx+1);
        board[r][c] = tmp;
        return found;
    };
    for (int r = 0; r < m; r++)
        for (int c = 0; c < n; c++)
            if (dfs(r, c, 0)) return true;
    return false;
}