What is the primary pattern used to solve the Word Search problem?

The primary pattern is backtracking search with pruning. By recursively exploring each cell and marking visited ones, unnecessary paths are eliminated.

How do you optimize the backtracking solution for Word Search?

Optimization comes from pruning invalid paths early, avoiding unnecessary recursion calls when a cell is out of bounds or the characters don’t match.

What are some common mistakes when solving Word Search using backtracking?

Common mistakes include failing to mark cells as visited or not handling edge cases like grid boundaries and revisiting cells.

Can the Word Search problem be solved iteratively?

While backtracking is the most natural solution for Word Search, it could be adapted to an iterative approach using a stack, but it would be less efficient.

What edge cases should be considered for Word Search?

Edge cases include when the word is longer than the grid, when no valid path exists, and when certain cells should not be revisited.

#79

Medium

auto_awesome回溯·pruning

LeetCode 题解工作台

单词搜索

给定一个 m x n 二维字符网格 board 和一个字符串单词 word 。如果 word 存在于网格中，返回 true ；否则，返回 false 。单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。示…

数组字符串回溯深度优先搜索矩阵

题目描述

给定一个 m x n 二维字符网格 board 和一个字符串单词 word 。如果 word 存在于网格中，返回 true ；否则，返回 false 。

单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。

示例 1：

输入：board = [['A','B','C','E'],['S','F','C','S'],['A','D','E','E']], word = "ABCCED"
输出：true

示例 2：

输入：board = [['A','B','C','E'],['S','F','C','S'],['A','D','E','E']], word = "SEE"
输出：true

示例 3：

输入：board = [['A','B','C','E'],['S','F','C','S'],['A','D','E','E']], word = "ABCB"
输出：false

提示：

m == board.length
n = board[i].length
1 <= m, n <= 6
1 <= word.length <= 15
board 和 word 仅由大小写英文字母组成

进阶：你可以使用搜索剪枝的技术来优化解决方案，使其在 board 更大的情况下可以更快解决问题？

lightbulb

解题思路

方法一：DFS(回溯)

我们可以枚举网格的每一个位置 $(i, j)$ 作为搜索的起点，然后从起点开始进行深度优先搜索，如果可以搜索到单词的末尾，就说明单词存在，否则说明单词不存在。

因此，我们设计一个函数 $dfs(i, j, k)$ ，表示从网格的 $(i, j)$ 位置出发，且从单词的第 $k$ 个字符开始搜索，是否能够搜索成功。函数 $dfs(i, j, k)$ 的执行步骤如下：

如果 $k = |word|-1$ ，说明已经搜索到单词的最后一个字符，此时只需要判断网格 $(i, j)$ 位置的字符是否等于 $word[k]$ ，如果相等则说明单词存在，否则说明单词不存在。无论单词是否存在，都无需继续往下搜索，因此直接返回结果。
否则，如果 $word[k]$ 字符不等于网格 $(i, j)$ 位置的字符，说明本次搜索失败，直接返回 false。
否则，我们将网格 $(i, j)$ 位置的字符暂存于 $c$ 中，然后将此位置的字符修改为一个特殊字符 '0'，代表此位置的字符已经被使用过，防止之后搜索时重复使用。然后我们从 $(i, j)$ 位置的上、下、左、右四个方向分别出发，去搜索网格中第 $k+1$ 个字符，如果四个方向有任何一个方向搜索成功，就说明搜索成功，否则说明搜索失败，此时我们需要还原网格 $(i, j)$ 位置的字符，即把 $c$ 放回网格 $(i, j)$ 位置（回溯）。

在主函数中，我们枚举网格中的每一个位置 $(i, j)$ 作为起点，如果调用 $dfs(i, j, 0)$ 返回 true，就说明单词存在，否则说明单词不存在，返回 false。

时间复杂度 $O(m \times n \times 3^k)$ ，空间复杂度 $O(\min(m \times n, k))$ 。其中 $m$ 和 $n$ 分别是网格的行数和列数；而 $k$ 是字符串 $word$ 的长度。

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

class Solution:
    def exist(self, board: List[List[str]], word: str) -> bool:
        def dfs(i: int, j: int, k: int) -> bool:
            if k == len(word) - 1:
                return board[i][j] == word[k]
            if board[i][j] != word[k]:
                return False
            c = board[i][j]
            board[i][j] = "0"
            for a, b in pairwise((-1, 0, 1, 0, -1)):
                x, y = i + a, j + b
                ok = 0 <= x < m and 0 <= y < n and board[x][y] != "0"
                if ok and dfs(x, y, k + 1):
                    return True
            board[i][j] = c
            return False

        m, n = len(board), len(board[0])
        return any(dfs(i, j, 0) for i in range(m) for j in range(n))

speed

复杂度分析

指标	值
时间	Depends on the final approach
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
Do you know how to implement backtracking to solve problems like Word Search?
question_mark
Can you explain the role of pruning in reducing the complexity of backtracking?
question_mark
Will you consider edge cases like grid boundaries and revisited cells in your solution?

warning

常见陷阱

外企场景

error
Forgetting to mark cells as visited during recursion, causing incorrect word matches.
error
Not pruning invalid paths early enough, leading to unnecessary and time-consuming searches.
error
Overlooking the case where the word exceeds the grid's size or cannot be constructed from adjacent cells.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Can you solve Word Search for larger grids (e.g., 10x10)?
arrow_right_alt
How would you handle a grid containing multiple occurrences of the target word?
arrow_right_alt
What if the board was a 2D matrix containing numbers instead of letters?

help

常见问题

外企场景

继续练习

#212 单词搜索 II #37 解数独 #130 被围绕的区域