Решить задачу Word Search (LeetCode 79)?

LeetCode 79. Найти слово в grid (последовательность соседних cells). DFS с backtracking, mark in-place.

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

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

    for r in range(rows):
        for c in range(cols):
            if board[r][c] == word[0] and dfs(r, c, 0):
                return True
    return False

Шаблон: explore → mark → recurse → unmark. Optimization: если count[word[0]] > count[word[-1]] — reverse word (начать с более редкой буквы = меньше стартовых точек). Word Search II (212) — много слов: построить Trie, DFS из каждой клетки. Без Trie — O(words × rows × cols × 4ᴸ), с Trie — O(rows × cols × 4ᴸ).