1

用 Go 剑指 Offer 12. 矩阵中的路径 （DFS + 回溯） - slowlydance2me

 1 year ago
source link: https://www.cnblogs.com/slowlydance2me/p/17303475.html
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
neoserver,ios ssh client

用 Go 剑指 Offer 12. 矩阵中的路径 （DFS + 回溯）

给定一个 m x n 二维字符网格 board 和一个字符串单词 word 。如果 word 存在于网格中，返回 true ；否则，返回 false 。

单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。

例如，在下面的 3×4 的矩阵中包含单词 "ABCCED"（单词中的字母已标出）。

 

2986763-20230410164948613-1796513803.png

输入：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
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

dfs + 回溯 解法

func exist(board [][]byte, word string) bool {
　　 wordb := []byte(word) // 转化一下 string 方便遍历
    rows := len(board)
    cols := len(board[0])

    for i := 0; i < rows; i++ {
        for j := 0; j < cols; j++ {
            if(dfs(board, wordb, i, j, 0)) { // 调用 dfs 函数
                return true
            }
        }
    }
    return false
}

func dfs(board [][]byte, wordb []byte, i int, j int, k int) bool {
    rows := len(board)
    cols := len(board[0])
//先考虑 false 情况：越界、不相等、重复
    if i >= rows || i < 0 || j >= cols || j < 0 || board[i][j] != wordb[k] {
        return false
    }
// 遍历完成返回true
    if k == len(wordb) - 1 {
        return true
    }
    //归零标记已遍历 byte 类型的0值为 0x0
    board[i][j] = 0x0

//四个方向遍历
    res := dfs(board, wordb, i + 1, j, k + 1) || dfs(board, wordb, i - 1, j , k + 1) || dfs(board, wordb, i, j + 1, k + 1) || dfs(board, wordb, i, j - 1, k + 1)
    board[i][j] = wordb[k]
    return res
}

__EOF__

本文作者： slowlydance2me 本文链接： https://www.cnblogs.com/slowlydance2me/p/17303475.html 关于博主： 评论和私信会在第一时间回复。或者直接私信我。 版权声明： 本博客所有文章除特别声明外，均采用 BY-NC-SA 许可协议。转载请注明出处！ 声援博主： 如果您觉得文章对您有帮助，可以点击文章右下角【推荐】一下。

report

Recommend

About Joyk


Aggregate valuable and interesting links.
Joyk means Joy of geeK