Sign in Subscribe
算法

单词搜索

loser

• 9 min read
Share

给定一个 m x n 二维字符网格 board 和一个字符串 word，判断 word 是否存在于网格中。

单词必须按照字母顺序，通过水平或垂直方向相邻的单元格构成。同一个单元格内的字母在一次搜索中不能重复使用。

示例 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 更大时加快搜索。

DFS + 回溯：

class Solution {
public:
    bool exist(vector<vector<char>>& board, string word) {
        int m = board.size();
        int n = board[0].size();
        int boardCount[128] = {};
        int wordCount[128] = {};

        for (const auto& row : board)
        {
            for (char ch : row)
            {
                ++boardCount[static_cast<unsigned char>(ch)];
            }
        }

        for (char ch : word)
        {
            ++wordCount[static_cast<unsigned char>(ch)];
        }

        for (int i = 0; i < 128; ++i)
        {
            if (wordCount[i] > boardCount[i])
            {
                return false;
            }
        }

        if (boardCount[static_cast<unsigned char>(word.front())]
            > boardCount[static_cast<unsigned char>(word.back())])
        {
            reverse(word.begin(), word.end());
        }

        int directions[4][2] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};

        for (int row = 0; row < m; ++row)
        {
            for (int col = 0; col < n; ++col)
            {
                if (board[row][col] == word[0]
                    && dfs(board, word, row, col, 0, directions))
                {
                    return true;
                }
            }
        }

        return false;
    }

private:
    bool dfs(
        vector<vector<char>>& board,
        const string& word,
        int row,
        int col,
        int index,
        int directions[4][2]
    )
    {
        if (index == word.size() - 1)
        {
            return true;
        }

        char original = board[row][col];
        board[row][col] = '#';
        int m = board.size();
        int n = board[0].size();

        for (int i = 0; i < 4; ++i)
        {
            int nextRow = row + directions[i][0];
            int nextCol = col + directions[i][1];

            if (nextRow < 0 || nextRow >= m || nextCol < 0 || nextCol >= n)
            {
                continue;
            }
            if (board[nextRow][nextCol] != word[index + 1])
            {
                continue;
            }
            if (dfs(board, word, nextRow, nextCol, index + 1, directions))
            {
                board[row][col] = original;
                return true;
            }
        }

        board[row][col] = original;
        return false;
    }
};

核心思想

这题可以把每个单元格看成搜索图中的一个节点，相邻的上下左右单元格之间存在边。

如果要匹配 word[index]，就需要从当前单元格出发，继续寻找四个方向中值为 word[index + 1] 的相邻单元格。

因此可以使用 DFS：

  1. 枚举每一个可能作为起点的单元格。
  2. 如果当前单元格等于当前需要匹配的字符，就继续向四个方向搜索。
  3. 搜索过程中暂时标记当前单元格，避免同一条路径重复使用它。
  4. 如果所有字符都匹配成功，返回 true。
  5. 如果当前方向搜索失败，撤销标记，尝试其他方向。

DFS 状态

递归函数表示：

dfs(board, word, row, col, index, directions)

其中：

  • row、col：当前所在单元格。
  • index：当前正在匹配 word[index]。
  • board：网格，同时用于记录当前路径中哪些单元格已被使用。
  • word：目标单词。

调用 dfs 时，已经保证：

board[row][col] == word[index]

所以递归函数只需要继续寻找下一个字符。

递归终止条件

当：

index == word.size() - 1

说明当前单元格已经匹配了单词的最后一个字符，整个单词搜索成功，直接返回 true。

如果搜索过程中没有找到合法的下一个单元格，当前路径失败，返回 false。

原地标记访问状态

代码使用字符 '#' 暂时标记当前单元格：

char original = board[row][col];
board[row][col] = '#';

由于题目保证网格中只包含大小写英文字母，'#' 不会和正常字符冲突。

当前路径搜索结束后，需要恢复原来的字符：

board[row][col] = original;

这一步就是回溯。如果不恢复，后续从其他起点搜索时会错误地认为某些单元格已经被使用。

四方向搜索

每次只搜索：

上：    (row - 1, col)
下：    (row + 1, col)
左：    (row, col - 1)
右：    (row, col + 1)

不搜索对角线方向，符合题目对相邻单元格的定义。

同时要检查坐标是否越界：

if (nextRow < 0 || nextRow >= m || nextCol < 0 || nextCol >= n)
{
    continue;
}

进阶剪枝一：字符频次预检查

如果 word 中某个字符出现次数多于 board 中该字符的总次数，那么无论如何都不可能找到这个单词。

例如：

board 中只有 2 个 A
word 中需要 3 个 A

可以直接返回 false，无需进入 DFS。

这一步不能单独证明单词一定存在，因为字符数量足够并不代表它们在网格中相邻，但可以提前排除一部分必不可能的情况。

进阶剪枝二：从稀有字符开始搜索

如果直接从 word[0] 开始搜索，起点数量可能很多。

由于反转单词不会改变“是否存在一条路径”的结论，因此可以比较：

  • word[0] 在网格中的出现次数
  • word.back() 在网格中的出现次数

如果末尾字符更少，就反转 word，从出现次数更少的一端开始搜索。

起点越少，DFS 的初始分支通常越少，实际运行速度会更快。

为什么标记时机很重要

当前单元格必须在继续搜索邻居之前就被标记：

board[row][col] = '#';

否则相邻单元格可能立即走回当前单元格，导致同一个单元格在同一条路径中被重复使用。

搜索失败后再恢复标记，能够保证：

  • 当前递归路径不会重复使用单元格。
  • 不同起点或不同分支之间不会互相影响。

正确性证明

结论 1：DFS 返回 true 时，网格中一定存在目标单词

只有当当前单元格等于 word[index] 时，算法才会进入对应的 DFS 状态。

递归向下扩展时，只会选择上下左右相邻、且等于下一个目标字符的单元格。

因此，从起点到终点形成的路径：

  • 每两个相邻单元格都满足题目要求的水平或垂直相邻关系。
  • 路径中的字符依次等于 word 中的字符。
  • 当前单元格在继续搜索前已被标记，不会在同一条路径中重复使用。

当到达最后一个字符时，得到的就是一个合法单词路径。

结论 2：所有可能的合法路径都会被搜索

算法会枚举网格中的每个单元格作为起点。

在每个搜索状态中，算法会枚举当前单元格的四个方向，并尝试所有满足下一个字符要求的相邻单元格。

因此，任意一条合法路径上的每一步选择都不会被算法遗漏。若存在合法路径，DFS 必然会沿着该路径搜索到最后一个字符。

结论 3：回溯不会错误排除其他路径

一个单元格只在当前递归路径中被临时标记。当前分支搜索结束后，算法会恢复它原来的字符。

因此，某条路径使用过的单元格不会永久影响其他起点或其他分支的搜索。

结论 4：字符频次和反转剪枝不会改变答案

如果单词中某个字符数量超过网格中的总数量，则不可能存在合法路径，直接返回 false 是正确的。

反转单词只改变路径匹配的方向。任意一条从起点到终点匹配原单词的路径，反过来就是一条匹配反转单词的路径，反之亦然。

因此，两个剪枝都不会改变最终判断结果。

综上，算法返回 true 当且仅当单词存在于网格中。

示例分析

以 word = "ABCCED" 为例，可以找到路径：

A -> B -> C -> C -> E -> D

对应坐标为：

(0,0) -> (0,1) -> (0,2) -> (1,2) -> (2,2) -> (2,1)

每一步都与前一个单元格水平或垂直相邻，并且没有重复使用单元格，因此返回 true。

对于 word = "ABCB"，虽然可以找到 A -> B -> C，但最后需要再次使用已经经过的 B，不允许重复使用同一个单元格，所以返回 false。

复杂度分析

设网格大小为 m x n，单词长度为 L。

  • 字符频次预检查：O(mn + L)。
  • DFS 最坏时间复杂度：O(mn * 4^L)。最多从 mn 个起点开始搜索，每一步最多尝试四个方向。
  • 空间复杂度：O(L)，主要是递归调用栈；网格标记使用原地修改，不额外开 visited 数组。

实际搜索中，当前单元格不能回到上一步使用过的单元格，因此后续分支通常少于 4^L；频次剪枝和稀有字符起点剪枝也会进一步减少搜索量。

边界情况

  • word 长度为 1：只需要判断网格中是否存在相同字符。
  • 网格中缺少 word 所需的某个字符：频次预检查会直接返回 false。
  • 单词需要重复经过同一个坐标：不允许，当前路径会通过 '#' 标记阻止回到该单元格。
  • 起点位于边界：越界方向会被直接跳过。
  • 所有搜索分支都失败：恢复所有临时标记后返回 false。