二维网格单词搜索

"单词搜索.md" 在这个问题中，我们面临的是一个典型的计算机科学算法题，具体来说是一个二维网格（board）中的单词搜索问题。给定一个由字母组成的矩阵（m x n），我们需要找出一个字符串（word）是否能按顺序通过矩阵中的相邻单元格构成。相邻的单元格可以是水平或垂直方向上的，但同一个单元格内的字母不能重复使用。 首先，我们可以用深度优先搜索（DFS，Depth-First Search）或者广度优先搜索（BFS，Breadth-First Search）来解决这个问题。这里提供的参考答案使用了深度优先搜索策略。 **DFS 解决方案的关键步骤：** 1. **初始化**：创建一个与输入矩阵 board 大小相同的二维整数数组 visited，用于标记已访问的单元格。所有初始值设为 -1，表示未访问。同时，我们需要一个字符串指针 k 来追踪当前匹配的单词位置。 2. **递归函数**：设计一个递归函数 `check`，接受四个参数：board、visited、当前坐标（i, j）和单词 s 的当前位置 k。如果 k 等于 word 的长度，说明已经找到了整个单词，返回 true；如果 i 或 j 越界，或者 board[i][j] 不等于 word[k]，返回 false。 3. **访问相邻单元格**：在确保 board[i][j] 等于 word[k] 的情况下，更新 visited[i][j] 为一个非负值，表示已经访问过，并递归检查上下左右四个相邻单元格。递归调用时，更新坐标 i 和 j，同时将 k 加一，指向下一个待匹配的字母。 4. **回溯**：在递归返回之前，将 visited[i][j] 重置为 -1，这是回溯操作，确保如果当前路径失败，不会影响其他可能的路径。 5. **主循环**：从矩阵的每个单元格开始，调用 `check` 函数，如果找到一个满足条件的路径，返回 true。如果所有可能的路径都尝试过但没有找到，返回 false。 **算法复杂度分析：** - 时间复杂度：O(m * n * (word.length + 1))，其中 m 和 n 分别是矩阵的行数和列数。最坏情况下，我们可能需要检查所有单元格和所有单词的子序列。 - 空间复杂度：O(m * n)，用于存储 visited 数组。 这个算法题考察了对基本数据结构（如二维数组）的理解，以及对搜索算法（DFS）的应用。它在编程面试和算法竞赛中常见，因为能够测试候选人的逻辑思维和问题解决能力。对于面试者来说，理解和熟练掌握这种问题的解决方案是提高技能的关键。