Word Search

Q: 单词搜索的时间复杂度是多少？

对于一个 m × n 的棋盘和一个长度为 L 的单词，时间复杂度为 O(m·n·3^L) ：每个单元格都可以作为路径的起点，第一步之后，每个单元格最多有三个未访问的邻居。递归所需的额外空间为 O(L) ，此外，复制棋盘还需要 O(m·n) 的空间。

中等回溯图

+10

你会得到一个字母网格 board，它是一个字符串列表，其中 board[r][c] 表示第 r 行、第 c 列的字母，以及一个字符串 word。

如果你能找到 word，就返回 true：从任意单元格开始，每次移动到上方、下方、左侧或右侧的单元格，使访问到的单元格按顺序拼出 word，且每个单元格只能使用一次。否则返回 false。字母区分大小写。

函数

exist(board: string-array, word: string) → boolean

boardstring-array: 网格，每行一串字母
wordstring: 要追踪的单词
返回值boolean: 无论单词能否通过并排的单元格追踪，每个单元格最多使用一次

约束条件

1 ≤ board.length ≤ 6
1 ≤ board[i].length ≤ 6，并且每一行的长度都相同。
1 ≤ word.length ≤ 20
board 和 word 只包含英文字母，包括大写和小写。

示例

输入: board = ["STAR", "POOL", "ENDS"]word = "STOOLS"
输出: true
解释: 从左上角的 S 开始，向右到 T，向下到 O，再向右到 O 和 L，然后向下到 L 下方的 S。每个格子都不重复。

输入: board = ["STAR", "POOL", "ENDS"]word = "POP"
输出: false
解释: 棋盘上有一个 P。在 P 和 O 之后，你还需要另一个 P，但唯一的 P 是起始格，不能重复使用。

输入: board = ["STAR", "POOL", "ENDS"]word = "SAND"
输出: false
解释: 棋盘上有 SAND 的每个字母，但唯一的 A 位于第 0 行、第 2 列，它与 S 都不相邻。

进阶

不只是回答“是”或“否”，你能数出棋盘上有多少种不同的 word 走法吗？

提示

逐个打开提示，每个都会多透露一点。

已打开 0/3

题解

你需要在网格中搜索路径。回溯会一次添加一个字母来延伸路径，并在路径经过某个单元格时将其标记，返回时取消标记，这样路径就不会重复使用同一个单元格。搜索的时间复杂度随单词长度呈指数增长，而 6 × 6 的棋盘可以支持这种搜索。

使用已访问网格进行回溯

思路

拼出前 i 个字母的路径，可以继续延伸到任意一个满足以下条件的相邻格子：其中的字母是 word[i]，并且该格子不在当前路径上。如果没有这样的相邻格子，路径就走到了死胡同，你需要退回。

撤销标记是保证算法正确的关键：死胡同路径经过的格子，必须能供下一次尝试使用。在 AA / AB 网格中查找 AAA 时，从左上角出发的两次尝试都会卡住。如果这些格子一直保持标记状态，就会漏掉答案：左下角，然后左上角，再到右上角。

第一步之后，每一步最多有 3 个新的方向可走，因此搜索最多可以探索 m·n·3^L 条路径。在一个由 A 组成的 5 × 5 网格中查找 8 个 A 后接一个 B 时，程序会检查大约 53,000 个格子，然后返回 false。

算法

创建一个 visited 网格，所有值均为 false。
dfs(r, c, i)：如果 (r, c) 超出网格范围、已访问，或不是 word[i]，则返回 false；如果 i 是最后一个索引，则返回 true。
否则，标记 (r, c)，用 i+1 尝试四个相邻位置，取消标记，然后返回是否有任何一次尝试成功。
如果从任意单元格开始调用 dfs(r, c, 0) 成功，则返回 true。

def exist(board, word):
    rows, cols = len(board), len(board[0])
    visited = [[False] * cols for _ in range(rows)]

    def dfs(r, c, i):
        # Can word[i:] be traced starting at cell (r, c)?
        if r < 0 or r >= rows or c < 0 or c >= cols:
            return False
        if visited[r][c] or board[r][c] != word[i]:
            return False
        if i == len(word) - 1:
            return True
        visited[r][c] = True   # mark: the current path owns this cell
        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))
        visited[r][c] = False  # restore: other paths may use it
        return found

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

使用原地标记和剪枝进行回溯

思路

保留搜索，只做两处改动。在棋盘的副本上用 # 标记单元格，回溯时再恢复原来的字母。# 永远不会匹配单词中的字母，因此字母检查也会排除路径上的单元格。

然后进行剪枝。如果单词需要的某个字母数量多于棋盘上该字母的数量，就返回 false：这样面对全是 A 的棋盘时，无需搜索就能得出答案。沿路径反向读取，会在相同的单元格上拼出反转后的单词，因此搜索反转后的单词会得到相同的答案。从单词两端中选择棋盘上较少见的字母作为起点：这样可作为起点的单元格更少，错误的起点也会立即失败。

如果唯一的 B 在一个夹在两个 C 之间的角落，正向搜索大约会检查 35,000 个单元格；反向搜索则只需检查 27 个。最坏情况仍为 O(m·n·3^L)。

算法

如果单词中某个字母的数量超过棋盘上的数量，则返回 false。
如果棋盘上 word[0] 的数量多于最后一个字母的数量，则反转 word。
将棋盘复制到一个可以修改的网格中。
dfs(r, c, i)：如果单元格不是 word[i]，则失败；如果到达最后一个索引，则成功；否则将其设为 #，尝试每个边界内的相邻单元格并传入 i+1，恢复该单元格，并返回是否有任意一次尝试成功。
如果从任意单元格开始调用 dfs 都能成功，则返回 true。

from collections import Counter


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

    # Pruning 1: the board must hold every letter as many times as the word uses it.
    have = Counter("".join(board))
    for letter, need in Counter(word).items():
        if have[letter] < need:
            return False

    # Pruning 2: a path read backwards is the same path, so start from the
    # end whose letter is rarer on the board: fewer cells begin a search.
    if have[word[0]] > have[word[-1]]:
        word = word[::-1]

    grid = [list(row) for row in board]

    def dfs(r, c, i):
        # Can word[i:] be traced starting at cell (r, c)?
        if grid[r][c] != word[i]:
            return False
        if i == len(word) - 1:
            return True
        grid[r][c] = "#"  # mark: "#" matches no letter, so this path cannot reuse the cell
        found = False
        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 dfs(nr, nc, i + 1):
                found = True
                break
        grid[r][c] = word[i]  # restore the letter for other paths
        return found

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

易错点和边界情况

失败分支后没有取消标记单元格：在 AA / AB 上搜索 AAA，结果为 false。
完全没有标记：路径会回到它最后经过的单元格，在示例棋盘上搜索 POP 会返回 true。
检查边界前先读取单元格：在 Python 中，board[-1] 是最后一行，因此路径会绕着网格循环。
移动后才检查是否成功：搜索 A 时，["A"] 必须返回 true。
通过交换单元格的大小写来标记：在 ["aA"] 上，被标记的 a 会被读作第二个 A，因此搜索 aAA 的结果为 true。

常见问题3

单词搜索的时间复杂度是多少？

对于一个 m × n 的棋盘和一个长度为 L 的单词，时间复杂度为 O(m·n·3^L)：每个单元格都可以作为路径的起点，第一步之后，每个单元格最多有三个未访问的邻居。递归所需的额外空间为 O(L)，此外，复制棋盘还需要 O(m·n) 的空间。

剪枝如何让单词搜索运行得更快？

先统计字母数量，如果棋盘上某个字母太少，就返回 false。然后从结尾开始搜索，使用更少见的字母，因为能以它开头的格子更少。这两项检查都不会改变最坏情况。

Word Search 和 Word Search II 有什么区别？

Word Search II 要求你找出列表中哪些单词出现在棋盘上。如果每个单词都搜索一次，就会重复工作，因此通常的解法是将单词放入字典树中，然后遍历一次棋盘；如果某条路径上的字母无法组成任何单词的开头，就放弃这条路径。

def exist(board, word):
    # 在这里编写代码

测试 #1

测试 #2

测试 #3

参数

board = ["STAR", "POOL", "ENDS"]
word = "STOOLS"

预期输出

true