leetcode:单词搜索

本文主要是介绍leetcode:单词搜索，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

思路：
1.遍历起点，给每个起点对应的visit数组
2.进入check函数进行bfs
3.若word长度没了，直接true（优先级最高）
4.越界处理false
5.不匹配false
5.进入bfs，先设置visit为真，然后立个flag记录上下左右的bool，最后把visit还回来，返回flag即可

代码：

func exist(board [][]byte, word string) bool {
    m := len(board)
    n := len(board[0])
    var visit [][]bool

    //遍历起点
    for i := 0; i < m; i++ {
        for j := 0; j < n; j++ {
            visit = make([][]bool, m)
            for k := 0; k < m; k++ {
                visit[k] = make([]bool, n)
            }
            if checkbfs(board, word, visit, i, j) {
                return true
            }
        }
    }
    return false
}

func checkbfs(board [][]byte, word string, visit [][]bool, r int, c int) bool {
    //正确退出(优先级第一！)
    if len(word) == 0 {
        return true
    }
    //边界处理
    m := len(board)
    n := len(board[0])
    if r >= m || r < 0 {
        return false
    }
    if c >= n || c < 0 {
        return false
    }

    //不匹配
    if word[0] != board[r][c] || visit[r][c] == true {
        return false
    }
    //进行bfs
    //fmt.Printf("r=%v, c=%v, now=%c\n", r, c, word[0])
    visit[r][c] = true
    flag := checkbfs(board, word[1:], visit, r + 1, c) ||
            checkbfs(board, word[1:], visit, r - 1, c) ||
            checkbfs(board, word[1:], visit, r, c + 1) ||
            checkbfs(board, word[1:], visit, r, c - 1) 
    visit[r][c] = false
    return flag
}

总结：
我居然自己写了出来
1.遍历起点+分配visit
2.正确退出条件
3.错误退出条件
4.锁定visit，四周bfs，解锁visit
5.返回flag

这篇关于leetcode:单词搜索的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！