图解单词搜索：用"蚂蚁觅食"理论一招制胜！

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

🌟 妙趣横生的生活场景

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

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

💡 题目剖析

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

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

让我们看个例子：

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

🤔 解题思路的演进

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

第一步：从何处开始？

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

第二步：怎么继续走？

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

第三步：避免走回头路

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

🚀 代码实现

class Solution {
    // 定义四个方向的移动
    private int[][] directions = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
    
    public boolean exist(char[][] board, String word) {
        int m = board.length, n = board[0].length;
        // 从每个位置开始尝试
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                // 找到可能的起点
                if (board[i][j] == word.charAt(0)) {
                    // 创建访问标记数组
                    boolean[][] visited = new boolean[m][n];
                    // 从这个位置开始搜索
                    if (dfs(board, word, i, j, 0, visited)) {
                        return true;
                    }
                }
            }
        }
        return false;
    }
    
    private boolean dfs(char[][] board, String word, int row, int col, 
                       int index, boolean[][] visited) {
        // 已经找到完整的单词
        if (index == word.length()) {
            return true;
        }
        
        // 越界检查
        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;
        
        // 向四个方向探索
        for (int[] dir : directions) {
            int newRow = row + dir[0];
            int newCol = col + dir[1];
            if (dfs(board, word, newRow, newCol, index + 1, visited)) {
                return true;
            }
        }
        
        // 回溯：恢复当前位置未访问状态
        visited[row][col] = false;
        return false;
    }
}

🎯 难点解析

1. 起点选择

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

2. 路径记录

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

3. 回溯处理

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

💡 优化思路

一些实用的优化技巧：

1. 提前判断：可以先检查矩阵中每个字母的出现次数，如果某个字母出现次数少于 word 中的出现次数，直接返回 false。

2. 方向选择优化：根据当前位置和目标单词的关系，可以优先选择更有可能成功的方向。

3. 空间优化：可以直接修改原矩阵来标记访问状态，省去 visited 数组。（面试时请先和面试官讨论是否允许修改输入）

🎯 相似题目引申

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

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

---

作者：忍者算法 公众号：忍者算法

🎁 回复【刷题清单】获取LeetCode高频面试题合集 🧑‍💻 回复【代码】获取多语言完整题解 💡 回复【加群】加入算法交流群，一起进步

#算法面试 #LeetCode #DFS #回溯算法