DEV Community
·
Leetcode 79：单词搜索
💡
原文英文，约500词，阅读约需2分钟。
📝
内容提要
给定一个 m x n 字符网格和一个字符串，判断该字符串是否存在于网格中。字符串可以通过相邻的水平或垂直单元格构成，且同一单元格不能重复使用。通过递归搜索四个方向查找字符，直到找到完整字符串或遍历所有单元格。
🎯
关键要点
- 给定一个 m x n 字符网格和一个字符串，判断该字符串是否存在于网格中。
- 字符串可以通过相邻的水平或垂直单元格构成，同一单元格不能重复使用。
- 通过递归搜索四个方向查找字符，直到找到完整字符串或遍历所有单元格。
- 示例测试用例包括不同的输入网格和字符串，输出结果为 true 或 false。
- 约束条件包括网格的大小和字符串的长度限制。
- 算法复杂度分析包括时间复杂度 O(row * col * 4 ^ word.length) 和空间复杂度 O(row * col)。
- 代码实现包括一个主方法和一个递归查找方法，处理边界条件和访问状态。
❓
延伸问答
如何判断一个字符串是否存在于字符网格中？
通过递归搜索相邻的水平或垂直单元格，直到找到完整字符串或遍历所有单元格。
在单词搜索中，字符网格的大小和字符串长度有什么限制？
字符网格的大小限制为 1 <= m, n <= 6，字符串长度限制为 1 <= word.length <= 15。
单词搜索的时间复杂度和空间复杂度是多少？
时间复杂度为 O(row * col * 4 ^ word.length)，空间复杂度为 O(row * col)。
在单词搜索中，如何处理已经访问的单元格？
使用一个布尔数组记录访问状态，访问后标记为已访问，搜索结束后再标记为未访问。
能否给出单词搜索的示例测试用例？
示例包括：输入 board = [['A','B','C','E'],['S','F','C','S'],['A','D','E','E']]，word = 'ABCCED'，输出为 true。
单词搜索的递归查找方法是如何工作的？
递归查找方法从当前单元格开始，检查四个方向的相邻单元格，直到找到字符或达到边界条件。
➡️
