jaryue
2023/04/09阅读:18主题:默认主题
leetcode剑指 Offer 12. 矩阵中的路径
题目描述
给定一个 m x n 二维字符网格 board 和一个字符串单词 word 。如果 word 存在于网格中,返回 true ;否则,返回 false 。
单词必须按照字母顺序,通过相邻的单元格内的字母构成,其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。
例如,在下面的 3×4 的矩阵中包含单词 "ABCCED"(单词中的字母已标出)。
示例 1:
输入:board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCCED" 输出:true 示例 2:
输入:board = [["a","b"],["c","d"]], word = "abcd" 输出:false
提示:
m == board.length n = board[i].length 1 <= m, n <= 6 1 <= word.length <= 15 board 和 word 仅由大小写英文字母组成
来源:力扣(LeetCode) 链接:https://leetcode.cn/problems/ju-zhen-zhong-de-lu-jing-lcof 著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
解题思路
法1
这个题要我们判断二维数组board中是否存在字符串word的所有 如果只是这个要求,我们可以直接用哈希表来解决,但是它还增加了一个条件,就是字母之间必须相邻,,也就是说word[0]与word[1]在board数组中位置必须是相邻的,可以是行相邻,也可以是列相邻,(相差一个位置),这样哈希表需要储存出现的位置信息,后期的逻辑就变得比较复杂,1.判断不能重复使用,2.判断不能超出数组边界同时不能漏掉数据,3. 相邻的字母的在board数组中的位置必须相同,必须满足所有的判断条件,不断先后索引,直到word中所有字母都在board中出现并且满足条件返回ture,如果不满足其中任何一个条件,就搜索下一个board中word的首字母,直到完全没有一个路线可以将整个word所有字母走完,返回false
-
遍历网格中的每个位置,如果某个位置的字符与单词的第一个字符相同,则从该位置开始进行搜索。
-
在搜索的过程中,需要判断当前位置是否越界、是否已经被访问过以及是否与单词中对应位置的字符相同。
-
如果搜索到单词的最后一个字符,则说明单词存在于网格中,返回 true。
-
如果搜索到某个位置无法继续搜索(即无法与单词中对应位置的字符相匹配),则需要回溯到上一个位置重新进行搜索。
-
时间复杂度(O(n^2)) -
空间复杂度(O(n^2))
法2
-
时间复杂度(O()) -
空间复杂度(O())
法3
-
时间复杂度(O()) -
空间复杂度(O())
执行结果
法1
func exist(board [][]byte, word string) bool {
m, n := len(board), len(board[0])
visited := make([][]bool, m)
for i := range visited {
visited[i] = make([]bool, n)
}
for i := 0; i < m; i++ {
for j := 0; j < n; j++ {
if dfs(board, visited, i, j, word, 0) {
return true
}
}
}
return false
}
func dfs(board [][]byte, visited [][]bool, i, j int, word string, k int) bool {
if board[i][j] != word[k] {
return false
} else if k == len(word)-1 {
return true
}
visited[i][j] = true
defer func() { visited[i][j] = false }()
if i > 0 && !visited[i-1][j] && dfs(board, visited, i-1, j, word, k+1) {
return true
}
if i < len(board)-1
作者介绍