DEV Community
·
Leetcode 79：单词搜索
内容提要
给定一个 m x n 字符网格和一个字符串，判断该字符串是否存在于网格中。字符串可以通过相邻的水平或垂直单元格构成，且同一单元格不能重复使用。通过递归搜索四个方向查找字符，直到找到完整字符串或遍历所有单元格。
关键要点
-
给定一个 m x n 字符网格和一个字符串，判断该字符串是否存在于网格中。
-
字符串可以通过相邻的水平或垂直单元格构成，同一单元格不能重复使用。
-
通过递归搜索四个方向查找字符，直到找到完整字符串或遍历所有单元格。
-
示例测试用例包括不同的输入网格和字符串，输出结果为 true 或 false。
-
约束条件包括网格的大小和字符串的长度限制。
-
算法复杂度分析包括时间复杂度 O(row * col * 4 ^ word.length) 和空间复杂度 O(row * col)。
-
代码实现包括一个主方法和一个递归查找方法，处理边界条件和访问状态。
延伸解读
算法复杂度分析
在解决单词搜索问题时，算法的时间复杂度为 O(row * col * 4 ^ word.length)，这意味着随着单词长度的增加，搜索的复杂度会显著上升。空间复杂度为 O(row * col)，主要用于存储访问状态。这提示我们在处理较大网格或较长单词时，可能会面临性能瓶颈。
递归搜索的注意事项
在实现递归搜索时，需要特别注意边界条件和访问状态的管理。确保不越界、不重复访问同一单元格是成功找到单词的关键。此外，回溯操作的正确性也至关重要，确保在每次递归后能够正确恢复访问状态，以便后续的搜索能够正常进行。
输入约束的影响
该问题的输入约束包括网格的大小和单词的长度限制，这对算法的设计和实现有直接影响。最大网格为 6x6，单词长度不超过 15，这意味着在实际应用中，算法可以在合理的时间内完成搜索。然而，超出这些限制可能导致算法效率下降或无法找到结果。
延伸问答
如何判断一个字符串是否存在于字符网格中？
通过递归搜索相邻的水平或垂直单元格，直到找到完整字符串或遍历所有单元格。
在单词搜索中，字符网格的大小和字符串长度有什么限制？
字符网格的大小限制为 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。
单词搜索的递归查找方法是如何工作的？
递归查找方法从当前单元格开始，检查四个方向的相邻单元格，直到找到字符或达到边界条件。
