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

上一篇:设计模式-》访问者模式


下一篇:C++关于树的一些常用代码实现