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
        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
        return found
    for r in range(rows):
        for c in range(cols):
            if dfs(r, c, 0): return True
    return False

                    [开始]
                  /    |    \
              选A      选B      选C
             / \      / \      / \
           ...  ...  ...  ... ...  ...

class Solution:
    def exist(self, board: list[list[str]], word: str) -> bool:
        rows, cols = len(board), len(board[0])
        
        def dfs(r: int, c: int, idx: int) -> bool:
            # Base case: matched all characters
            if idx == len(word):
                return True
            
            # Boundary + character check — prune early!
            if (r < 0 or r >= rows or
                c < 0 or c >= cols or
                board[r][c] != word[idx]):
                return False
            
            # Mark as visited by temporarily overwriting
            # This is the "in-place" trick: no extra set needed
            temp = board[r][c]
            board[r][c] = '#'   # 标记已访问 / mark visited
            
            # Explore all 4 directions
            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)
            )
            
            # Undo the mark — this is the "backtrack" step
            board[r][c] = temp  # 撤销标记 / restore
            
            return found
        
        # Try every cell as the starting point
        for r in range(rows):
            for c in range(cols):
                if dfs(r, c, 0):
                    return True
        return False

class Solution:
    def exist(self, board: list[list[str]], word: str) -> bool:
        rows, cols = len(board), len(board[0])
        
        # ============================================================
        # PRUNING #1: Frequency check — O(M*N + L), saves huge time
        # 如果 board 里某个字母的数量 < word 里需要的数量，直接返回 False
        # ============================================================
        from collections import Counter
        board_count = Counter(c for row in board for c in row)
        word_count  = Counter(word)
        for ch, cnt in word_count.items():
            if board_count[ch] < cnt:
                return False
        
        # ============================================================
        # PRUNING #2: Reverse word if tail is rarer than head
        # 从频率更低的一端开始搜索 → 更快剪枝
        # Example: word="AAAAAB" → start from 'B' side
        # ============================================================
        if board_count[word[0]] > board_count[word[-1]]:
            word = word[::-1]
        
        def dfs(r: int, c: int, idx: int) -> bool:
            if idx == len(word):
                return True
            if (r < 0 or r >= rows or
                c < 0 or c >= cols or
                board[r][c] != word[idx]):
                return False
            
            temp = board[r][c]
            board[r][c] = '#'
            
            # ============================================================
            # PRUNING #3: Short-circuit with 'or' — stops at first True
            # Python 'or' short-circuits: once one branch returns True,
            # the remaining branches are not evaluated
            # ============================================================
            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
            return found
        
        for r in range(rows):
            for c in range(cols):
                # ============================================================
                # PRUNING #4: Skip starting cells that don't match word[0]
                # (implicit in dfs check, but can also be explicit)
                # ============================================================
                if dfs(r, c, 0):
                    return True
        return False

# Option A: In-place overwrite (推荐 / Recommended)
# Pros: O(1) extra space, clean
# Cons: board is mutated during search (not thread-safe)
temp = board[r][c]
board[r][c] = '#'
# ... recurse ...
board[r][c] = temp

# Option B: visited set
# Pros: board unchanged, intuitive
# Cons: O(M*N) extra space, set add/remove overhead
visited = set()
visited.add((r, c))
# ... recurse ...
visited.remove((r, c))

# Option C: bitmask (for very small grids, e.g., 4x4)
# Pros: O(1) space, fast bitwise ops
# Cons: only works when M*N ≤ 64
mask |= (1 << (r * cols + c))
# ... recurse ...
mask ^= (1 << (r * cols + c))  # XOR to unset

class TrieNode:
    def __init__(self):
        self.children: dict[str, 'TrieNode'] = {}
        self.word: str | None = None  # store complete word at leaf

class Solution:
    def findWords(self, board: list[list[str]], words: list[str]) -> list[str]:
        # Build Trie from all words
        root = TrieNode()
        for w in words:
            node = root
            for ch in w:
                node = node.children.setdefault(ch, TrieNode())
            node.word = w  # mark end of word
        
        rows, cols = len(board), len(board[0])
        result = []
        
        def dfs(r: int, c: int, node: TrieNode) -> None:
            ch = board[r][c]
            
            # KEY: check if this character exists in Trie
            # If not, prune entire subtree — this is the Trie speedup
            if ch not in node.children:
                return
            
            next_node = node.children[ch]
            
            # Found a complete word
            if next_node.word:
                result.append(next_node.word)
                next_node.word = None  # de-duplicate: don't add same word twice
            
            # Mark visited
            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  # restore
            
            # Optimization: prune empty Trie nodes (leaf pruning)
            # If next_node has no more children and no word,
            # remove it from parent to speed up future searches
            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

class Solution:
    def solveNQueens(self, n: int) -> list[list[str]]:
        result = []
        
        # Track which columns, diagonals are under attack
        # 用 set 追踪哪些列、对角线、反对角线已被攻击
        cols    = set()
        diag    = set()   # r - c is constant along a diagonal
        anti    = set()   # r + c is constant along anti-diagonal
        
        board = [['.'] * n for _ in range(n)]
        
        def backtrack(row: int) -> None:
            # Base case: placed queens in all n rows
            if row == n:
                result.append([''.join(r) for r in board])
                return
            
            for col in range(n):
                # Constraint check — prune invalid placements
                if col in cols or (row - col) in diag or (row + col) in anti:
                    continue
                
                # Choose
                cols.add(col)
                diag.add(row - col)
                anti.add(row + col)
                board[row][col] = 'Q'
                
                # Recurse
                backtrack(row + 1)
                
                # Undo
                cols.discard(col)
                diag.discard(row - col)
                anti.discard(row + col)
                board[row][col] = '.'
        
        backtrack(0)
        return result

For any cell (r, c):
  - Same diagonal:       r - c = constant
  - Same anti-diagonal:  r + c = constant

Example (4x4):
r-c diagonals:       r+c anti-diagonals:
-3 -2 -1  0          0  1  2  3
-2 -1  0  1          1  2  3  4
-1  0  1  2          2  3  4  5
 0  1  2  3          3  4  5  6

# ❌ Gotcha 1: Forgetting to restore board[r][c]
# 最常见错误：忘记撤销 in-place 标记
# If you mark '#' but don't restore, later DFS branches see '#'
board[r][c] = '#'
result = dfs(...)
# MUST restore before returning!
board[r][c] = temp  # ← don't forget this

# ❌ Gotcha 2: Off-by-one in base case
# idx == len(word) means we matched ALL characters
# Some people write idx == len(word) - 1 → misses last char
if idx == len(word):   # ✅ correct
    return True
if idx == len(word) - 1 and board[r][c] == word[idx]:  # ✅ also correct
    return True

# ❌ Gotcha 3: Word Search II — duplicate results
# If the same word can be found via multiple paths,
# de-duplicate by clearing node.word after first find
if next_node.word:
    result.append(next_node.word)
    next_node.word = None  # ← prevent duplicates

# ❌ Gotcha 4: Empty board / single cell
board = [["a"]]
word = "a"   # → True (idx hits len(word) immediately after matching)
word = "aa"  # → False (can't reuse cell, no neighbors)

# ❌ Gotcha 5: N-Queens — using list for cols check
# O(n) lookup per placement → O(n^3) total
# Use set for O(1) lookup → O(n^2) total