79. 单词搜索#

今天我们来挑战一道非常有意思的题目 - LeetCode 79「单词搜索」。这道题不少同学第一次见时都会有点懵，但别担心，跟着我用”蚂蚁觅食”的思路，保证让你豁然开朗！

🌟 妙趣横生的生活场景#

想象一下，你是一只正在寻找食物的小蚂蚁。你站在一片格子状的区域里，需要找到一条通往食物的路径。每走一步只能在上下左右四个方向移动，而且为了避免兜圈子，走过的格子就不能再走了。

这不就是我们在字母矩阵中搜索单词的过程吗？每个字母就像是一个路标，我们需要找到一条路径，让这些路标连起来正好拼成目标单词。

问题描述#

题目目标#

给定一个 m x n 的字符网格 board 和一个字符串 word ，判断 word 是否存在于网格中。单词必须通过相邻单元格内的字母构成，相邻单元格是水平或垂直相邻的，同一个单元格内的字母不能被重复使用。

示例 1#

输入：

board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCCED"

text

输出： true 网格示意：

A B C E
S F C S
A D E E

text

说明： 图示把输入结构和输出结果并排展开后，会更容易直接看清题目的变化过程。

💡 题目剖析#

题目要求：给定一个 m x n 的字符矩阵 board 和一个字符串 word，如果 word 在矩阵中存在，返回 true；否则返回 false。规则是：

单词必须按照字母顺序，通过相邻的单元格内的字母构成
相邻单元格就是字母周围上、下、左、右四个方向
同一个单元格内的字母不允许被重复使用

让我们看个例子：

board = [
  ['A','B','C','E'],
  ['S','F','C','S'],
  ['A','D','E','E']
]
word = "ABCCED"  // 返回 true

plaintext

🤔 解题思路的演进#

让我们像教小朋友玩游戏一样，一步步理解解决方案：

第一步：从何处开始？#

就像蚂蚁需要先找到起点一样，我们要先找到单词的第一个字母。这个字母可能在矩阵的任何位置，所以我们需要搜索整个矩阵来找可能的起点。

第二步：怎么继续走？#

找到起点后，就像蚂蚁循着气味寻找食物，我们需要看看四周的字母是否匹配单词的下一个字母。这就用到了经典的深度优先搜索（DFS）策略。

第三步：避免走回头路#

蚂蚁会留下信息素标记走过的路，我们也需要标记已经使用过的字母，避免重复使用。这可以通过一个访问标记数组来实现。

🚀 代码实现#

class Solution {
    // directions：四联通方向数组，分别表示上、下、左、右
    private int[][] directions = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};

    // 主函数：判断 word 是否能在 board 中按规则被找到
    public boolean exist(char[][] board, String word) {
        // m、n：矩阵的行数和列数
        int m = board.length, n = board[0].length;

        // 枚举每个格子，尝试把它作为单词首字母的起点
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                // 只有当当前格子字符等于 word 第一个字符时，才有必要开始 DFS
                if (board[i][j] == word.charAt(0)) {
                    // visited：记录本次搜索路径上已访问的格子，避免重复使用同一格
                    boolean[][] visited = new boolean[m][n];

                    // 从 (i, j) 开始，匹配 word 的第 0 个字符
                    if (dfs(board, word, i, j, 0, visited)) {
                        // 只要有一条路径匹配成功，立即返回 true
                        return true;
                    }
                }
            }
        }

        // 所有起点都尝试失败，返回 false
        return false;
    }

    // DFS：从 board[row][col] 出发，尝试匹配 word[index...] 
    private boolean dfs(char[][] board, String word, int row, int col, 
                       int index, boolean[][] visited) {
        // 终止条件：index 到达 word 长度，说明前面的字符都已成功匹配
        if (index == word.length()) {
            return true;
        }

        // 边界与合法性检查（任一不满足都直接失败）：
        // 1) 坐标越界
        // 2) 该格子已在当前路径中使用过
        // 3) 当前格子字符与目标字符 word[index] 不匹配
        if (row < 0 || row >= board.length || col < 0 || col >= board[0].length 
            || visited[row][col] || board[row][col] != word.charAt(index)) {
            return false;
        }

        // 做选择：标记当前位置已访问，加入当前路径
        visited[row][col] = true;

        // 继续向四个方向搜索下一个字符（index + 1）
        for (int[] dir : directions) {
            // newRow/newCol：下一个要探索的相邻位置
            int newRow = row + dir[0];
            int newCol = col + dir[1];

            // 只要某个方向能匹配成功，立即返回 true（短路）
            if (dfs(board, word, newRow, newCol, index + 1, visited)) {
                return true;
            }
        }

        // 撤销选择（回溯）：当前路径走不通，恢复现场供其他分支使用
        visited[row][col] = false;
        return false;
    }
}

java

🎯 难点解析#

1. 起点选择#

很多同学一开始就卡在了”从哪里开始找”这个问题上。实际上，我们需要尝试每个可能的起点，只要找到一条路径就可以了。这就像蚂蚁在找食物时，会从不同的位置出发探索。

2. 路径记录#

如何避免重复使用字母？我们使用了一个 visited 数组来标记已经访问过的位置。这就像蚂蚁留下的信息素，告诉自己”这条路已经走过了”。

3. 回溯处理#

当一条路径走不通时，我们需要恢复现场，尝试其他路径。这就是为什么我们在探索完一个方向后，要把 visited 标记重置为 false。

💡 优化思路#

一些实用的优化技巧：

提前判断：可以先检查矩阵中每个字母的出现次数，如果某个字母出现次数少于 word 中的出现次数，直接返回 false。
方向选择优化：根据当前位置和目标单词的关系，可以优先选择更有可能成功的方向。
空间优化：可以直接修改原矩阵来标记访问状态，省去 visited 数组。（面试时请先和面试官讨论是否允许修改输入）

🎯 相似题目引申#

这道题的解题思路可以应用到很多类似的问题上：

岛屿数量（LeetCode 200）
矩阵中的最长递增路径（LeetCode 329）
单词搜索 II（LeetCode 212）