LC79　单词搜索¶

中等通过率 51.4%python3核心代码模式回溯样例通过牛客 AC深度优先搜索数组字符串回溯矩阵

一句话

以每个格子为起点做深搜，沿途把走过的格子原地改写成占位符防止绕回来。

解题思路¶

这题考什么¶

要找的是一条简单路径：格子四连通、字母依次匹配 word、同一格不能重复使用。起点未知，所以枚举全部 m*n 个格子当起点；从某个起点出发后，第 k 步必须踩到 word[k]，踩不上就当场回头——这条剪枝把绝大多数分支砍在第一两步。

board = A B C E      word = "ABCCED"
        S F C S      (0,0)A -> (0,1)B -> (0,2)C -> (1,2)C -> (2,2)E -> (2,1)D
        A D E E      六步全部匹配，返回 true

「同一格不能重复使用」必须靠标记维护。本文件把当前格暂存到局部变量、原地改写成空串这个不可能等于任何字母的占位符，四个方向递归完再写回去—— 这比额外开一份 visited 数组省一份 m*n 的空间，代价是入参被临时修改。

还原是必须的，不是可选的：标记表达的是「这一格在当前这条路径上已被占用」，而不是「这一格永远不能再用」。同一格完全可能出现在另一条起点或另一条走法的路径里（示例 2 的 "SEE" 与示例 1 的 "ABCCED" 就共用了若干格子）。不还原等于把它从棋盘上永久抹掉，后续搜索会漏掉真实存在的解，返回假的 false。回溯的「选择 -> 递归 -> 撤销」三步见 DFS 深度优先搜索。

题面「进阶」问的搜索剪枝，本文件用了两条开搜之前就能判的廉价剪枝，两条都只花一次 O(m*n + L) 的统计：其一，字符总量：word 里某个字母的个数超过棋盘上该字母的总数，必然拼不出来。其二，从稀有的一端起步：一条路径正着走能拼出 word，反过来走就能拼出反转的 word，两者存在性完全等价。所以当 word 末字符在棋盘上比首字符更少时，把 word 反转再搜，起点候选数直接从「首字符的出现次数」降到「末字符的出现次数」。

数据规模与复杂度¶

1 <= m, n <= 6（最多 36 格），1 <= word.length <= 15。每个起点出发后，第一步有 4 个方向，之后每步最多 3 个（来路那格已被标记），单个起点的分支上界 O(4 乘 3 的 (L-1) 次方)，L = 15 时理论值极大；字母匹配这条剪枝在真实数据上让绝大多数分支活不过两三步，实测是微秒级。真正撑开搜索树的是对抗性用例。本地实测（6x6 棋盘）： 36 格全是 'a'，word 由 14 个 'a' 加末尾一个 'b' 组成（共 15 字符）时，不加任何预剪枝要跑 1.31 秒；字符总量剪枝一眼看出棋盘上没有 'b'，直接 0 秒返回。棋盘只在两个对角上各放一个 'b'、word 由 13 个 'a' 加末尾两个 'b' 组成时，字符总量这关能过（'b' 恰好够两个），不反转要跑 0.59 秒；按稀有端反转后起点只剩两个、第二步就断，同样 0 秒。空间 O(L)：只有递归栈，标记是就地写在 board 上的，不额外开数组。

坑在哪¶

还原标记必须覆盖所有返回路径，包括「找到了，返回 true」那一条。只在失败时还原，成功路径上的格子会一直留着占位符，board 被永久破坏；判题虽只看返回值，但函数不该留下这种副作用，同一张盘再调一次就会出错。
占位符要选一个不可能出现在 word 里的值。题面保证 board 与 word 都只含英文字母，用空串（或 '#'）都安全；绝不能用某个字母，否则会与真实字符撞车，把走过的格子误判成可继续匹配。
越界判断要写在取 board[nx][ny] 之前。Python 的负下标会绕回去读到对侧的格子，漏掉 0 <= nx 这一半条件时，第 0 行的上邻居会读成最后一行，凭空造出一条不存在的通路。
匹配成功的出口是 k == len(word) - 1，即踩中最后一个字母时就返回 true。写成 k == len(word) 再判会多走一步，还得额外处理「word 走完但当前格越界」的情况。
反转 word 这条剪枝之所以成立，是因为路径没有方向性：格子序列反过来读仍是一条合法的四连通简单路径。若题目改成「只能向右或向下走」，路径带了方向，这条剪枝立刻失效。
起点循环里一旦某个起点返回 true 就要立刻 return，不能继续扫。虽然结果一样，但最坏情况下会把 36 个起点全跑一遍，白花几十倍时间。

样例复核¶

示例 3 的 word = "ABCB"：棋盘上 'B' 有 1 个而 word 要 2 个，字符总量剪枝当场返回 false，与样例一致。去掉这条剪枝走完整搜索也是 false：从 (0,0) 出发 A、B、C 匹配到 (0,2)，第四个字母 B 要求 (0,2) 的邻居里有 B——上方越界、下方是 C、右边是 E、左边的 (0,1) 正是 B 却已被标记占用，四个方向全断。

参考实现¶

solutions/leetcode/LC79/sol.py
from collections import Counter
from typing import List, Optional


class Solution:
    def exist(self, board: List[List[str]], word: str) -> bool:
        m, n = len(board), len(board[0])
        # 简单路径最长只有 m*n 格，单词比棋盘还长时直接否掉，省一整棵搜索树
        if len(word) > m * n:
            return False

        # 预剪枝一：棋盘上某个字母的总数不够 word 用，怎么走都拼不出来。
        # 全 'a' 的棋盘配含 'b' 的 word 是最典型的对抗用例，这一句把它从 1.3 秒压到 0 秒
        board_cnt = Counter(ch for row in board for ch in row)
        for ch, need in Counter(word).items():
            if board_cnt[ch] < need:
                return False
        # 预剪枝二：路径没有方向性，正着能拼出 word 等价于反着能拼出反转的 word。
        # 于是从棋盘上更稀有的那一端起步，起点候选数直接降到该字母的出现次数
        if board_cnt[word[-1]] < board_cnt[word[0]]:
            word = word[::-1]

        def dfs(x: int, y: int, k: int) -> bool:
            # 当前格对不上 word 的第 k 个字母就立刻回头，这是搜索过程中最有效的剪枝
            if board[x][y] != word[k]:
                return False
            # 踩中最后一个字母即算找到；写成 k == len(word) 会多走一步、多出边界分支
            if k == len(word) - 1:
                return True
            # 选：暂存原字符，原地改成空串。空串不等于任何字母，
            # 于是这一格在本条路径的后续步骤里自然匹配不上，等价于「已访问」
            tmp = board[x][y]
            board[x][y] = ""
            for nx, ny in ((x - 1, y), (x + 1, y), (x, y - 1), (x, y + 1)):
                # 先判越界再递归：负下标会绕回对侧，凭空造出不存在的通路
                if 0 <= nx < m and 0 <= ny < n and dfs(nx, ny, k + 1):
                    # 成功路径上也要还原，否则 board 被永久改坏，再次调用就会出错
                    board[x][y] = tmp
                    return True
            # 撤销：标记只表示「在当前这条路径上被占用」，换一条路径这一格还能再走
            board[x][y] = tmp
            return False

        # 起点未知，逐格尝试；一旦成功立刻返回，不必把剩下的起点也跑一遍
        for i in range(m):
            for j in range(n):
                if dfs(i, j, 0):
                    return True
        return False

LC79 单词搜索¶