LeetCode79:单词搜索(WordSearch)

LeetCode 79: 单词搜索 (Word Search)

题目描述： 给定一个字母矩阵 board 和一个目标单词 word，判断该单词是否可以从矩阵中按以下规则组成：

单词中的字母必须按顺序通过相邻的单元格（上下左右四方向）。同一个单元格内的字母不允许重复使用。

---

题解思路

这是一个经典的二维网格搜索问题，本质是通过深度优先搜索 (DFS) 在二维矩阵内寻找路径，同时要避免重复访问。以下是解题的关键点：

递归回溯： DFS 是核心，一旦尝试了一个方向不满足条件，就需要回溯重新尝试其他方向。

边界条件：

如果超过矩阵边界，或者当前字母与目标单词不匹配，停止搜索。必须检查所有方向（上、下、左、右）。

标记已访问：

为了避免重复访问，可以在当前路径中标记节点为已访问。方法是用一个布尔型数组 visited，或者在 board 上直接修改字符（临时替换）。

---

解法 1：回溯 DFS

我们可以从二维网格的每一个位置出发，尝试寻找目标单词，依次搜索上下左右方向。

模板代码 class Solution { public boolean exist(char[][] board, String word) { int rows = board.length, cols = board[0].length; // 遍历二维矩阵的每一个位置作为起点 for (int i = 0; i < rows; i++) { for (int j = 0; j < cols; j++) { if (dfs(board, word, i, j, 0)) { // 从每个起点开始深度优先搜索 return true; } } } return false; } private boolean dfs(char[][] board, String word, int i, int j, int index) { // 边界条件：单词匹配完成 if (index == word.length()) return true; // 边界条件：越界或字母不匹配 if (i < 0 || i >= board.length || j < 0 || j >= board[0].length || board[i][j] != word.charAt(index)) { return false; } // 临时标记当前节点为访问过（如替换字符） char temp = board[i][j]; board[i][j] = '#'; // 递归搜索四个方向 boolean found = dfs(board, word, i + 1, j, index + 1) || dfs(board, word, i - 1, j, index + 1) || dfs(board, word, i, j + 1, index + 1) || dfs(board, word, i, j - 1, index + 1); // 回溯，将当前节点恢复为未访问状态 board[i][j] = temp; return found; } } 时间和空间复杂度分析 时间复杂度：O(M * N * 4^L) 网格大小为 M x N，每个点最多递归 4 个方向，单词长度为 L。最差情况下，每个单词字符均需遍历整个搜索树。 空间复杂度：O(L) 递归函数的栈深度为单词长度 L，无其他额外存储。

---

解法 2：BFS 图搜索

相较于 DFS 的递归方式，BFS 使用队列逐层搜索，可以更好控制空间消耗。但实现较为复杂。

思路 使用队列同时存储坐标和单词匹配的位置。对每个队列中的坐标，向四个方向扩展，直到找到完整单词或队列为空。 注意

由于 BFS 不如 DFS 直观，而且未必能直接操作矩阵，因此在竞赛中很少使用 BFS 解法。

模板代码 // BFS实现为非递归

---

解法 3：Trie + DFS

如果我们需要寻找多个单词，可使用 前缀树 (Trie) 优化搜索过程（见变体题目）。

---

常见变体及高级模板 变体 1：LeetCode 212. 单词搜索 II

问题描述： 给定一个二维字符网格和一个单词数组，找到所有可以在网格中搜索到的单词。

分析与解法：

如果对于每个单词都从网格出发执行 DFS，则时间复杂度会很高。可使用 前缀树 (Trie) 来高效管理单词集合，降低搜索次数。

模板代码 (Trie + DFS)：

class Solution { public List<String> findWords(char[][] board, String[] words) { List<String> result = new ArrayList<>(); Trie trie = new Trie(); // 构建前缀树 for (String word : words) { trie.insert(word); } int rows = board.length, cols = board[0].length; // 遍历网格中每一个点，尝试匹配 for (int i = 0; i < rows; i++) { for (int j = 0; j < cols; j++) { dfs(board, trie.root, i, j, result); } } return result; } private void dfs(char[][] board, TrieNode node, int i, int j, List<String> result) { if (i < 0 || i >= board.length || j < 0 || j >= board[0].length || board[i][j] == '#') { return; } char c = board[i][j]; if (!node.children.containsKey(c)) return; node = node.children.get(c); if (node.word != null) { // 找到一个完整单词 result.add(node.word); node.word = null; // 避免重复添加 } // 标记并递归 board[i][j] = '#'; dfs(board, node, i + 1, j, result); dfs(board, node, i - 1, j, result); dfs(board, node, i, j + 1, result); dfs(board, node, i, j - 1, result); board[i][j] = c; // 回溯 } } // 前缀树节点定义 class TrieNode { Map<Character, TrieNode> children; String word; public TrieNode() { children = new HashMap<>(); word = null; } } // 前缀树实现 class Trie { public TrieNode root; public Trie() { root = new TrieNode(); } public void insert(String word) { TrieNode node = root; for (char c : word.toCharArray()) { node.children.putIfAbsent(c, new TrieNode()); node = node.children.get(c); } node.word = word; } } 时间和空间复杂度： 构建 Trie 的时间复杂度：O(L)，其中 L 为所有单词长度和。搜索时间复杂度：O(M * N * 4^K)，其中 K 是单词平均长度。空间复杂度：O(L + K)，Trie 的存储空间 + DFS 栈深度。

---

变体 2：变形规则的路径搜索 二维迷宫 (Maze) 问题：是否存在从起点到终点的路径？ 核心思路与单词搜索相似，使用 DFS 或 BFS 找到可达路径。 二维矩阵的最长递增路径 (LeetCode 329)： 从每个点出发递归搜索，以动态规划方式记录当前点为起点的最长路径。

---

快速 AC 总结

单词搜索 I：

使用经典 DFS + 回溯，控制好边界条件，标记已访问节点。优先练习模板来快速 AC。

单词搜索 II：

借助前缀树 (Trie) 优化搜索，大幅减少冗余路径搜索。理解 Trie 的构建与节点管理逻辑。

变体题目：

DFS 在二维问题中非常通用，可迁移到迷宫、岛屿问题等。动态规划可以与 DFS 结合，缓存中间结果提升性能。

---

通过练习这些模板和快速套用对应技巧，你可以轻松在比赛中快速 AC！