Bloomberg Word Search：网格 DFS 回溯与单路径不可复用

题意与假设

这道练习题保留了面经中值得训练的核心约束，并将需要澄清的条件单独列出。现场拿到变体时，先和面试官确认这些条件。

• 训练版四方向相邻，每个格子在同一匹配路径中最多使用一次，返回 bool；空词定义为 true。
• 题目未明确具体 board 或字符集，本文只说明通用约束。

解题路线

1. 从 board 每个可能匹配 word[0] 的格子启动 DFS(index,r,c,used)。
2. 字符不合直接失败；最后一个字符匹配即成功。否则暂时标记当前格已用，递归四邻，回溯时撤销标记。
3. 提前比较 word 频次与 board 频次可剪枝；还可从稀有端倒序搜索，但需先保证原问题只是存在性。
4. BFS 若把 used 集合作为状态会产生大量路径副本，不能只按格子 visited；DFS 工作栈通常更省。

手动走一遍

board=[[A,B],[C,D]]，word=‘ABD’：A→B→D 可达；word=‘ABA’ 不能重用 A 格，故失败。

Python 参考实现

下面的代码按上文假设实现，适合本地运行并追加自己的测试用例。

代码区可横向滚动；使用键盘时，先聚焦代码区再按方向键查看。

def exists_word(board, word):
    """4-neighbor path; a cell is used at most once in a path."""
    if word == "":
        return True
    if not board or not board[0]:
        return False
    rows, cols = len(board), len(board[0])
    if any(len(row) != cols for row in board):
        raise ValueError("board must be rectangular")
    used = set()

    def dfs(r, c, index):
        if board[r][c] != word[index]:
            return False
        if index + 1 == len(word):
            return True
        used.add((r, c))
        for nr, nc in ((r + 1, c), (r - 1, c), (r, c + 1), (r, c - 1)):
            if 0 <= nr < rows and 0 <= nc < cols and (nr, nc) not in used:
                if dfs(nr, nc, index + 1):
                    used.remove((r, c))
                    return True
        used.remove((r, c))
        return False

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

复杂度

R×C 起点、长度 L，保守 O(RC·4^L) 时间，单路径 visited/递归 O(L) 空间；指数来自路径选择。

易错点与追问

容易失分的边界

• 全局 visited 阻止其他起点重试。
• 同一路径复用同格。
• 成功/失败返回前忘记恢复标记。
• 声称普通 BFS 只需 O(RC) 状态。

继续深挖

• 有多个单词如何用 Trie 共享前缀？
• 递归深度太大怎么办？
• 如何用字符频次剪枝？