[数据结构与算法]LeetCode 打卡 Day 39 —— 单词搜索

1、题目

2、题解

看完题目后并没有想到较为简单的解决方法，所以准备暴力解题了，回溯吧，排除掉错误的答案，最后代码如下

func exist(board [][]byte, word string) bool {
    m := len(board)
    n := len(board[0])
    l := len(word)
    wordByte := []byte(word)
    isUsed := make([][]bool, m)
    for b := range isUsed {
        isUsed[b] = make([]bool, n)
    }

    var dfs func (i, j, index int) bool 
    dfs = func (i, j, index int) bool{
        // fmt.Println("----", i, j, index)
        if i>=m || i<0 || j>=n || j<0 {
            return false
        }
        if board[i][j] == wordByte[index] && !isUsed[i][j]{
            // fmt.Println("+")
            isUsed[i][j]=true
            
            if index == l-1 {                     //存在单词
                return true
            }
            
            if dfs(i+1, j, index+1) {
                return true
            }
            if dfs(i, j+1, index+1) {
                return true
            }
            if dfs(i-1, j, index+1) {
                return true
            }
            if dfs(i, j-1, index+1) {
                return true
            }
            defer func(){isUsed[i][j]=false}()
        }
        return false
    }
    for p:=0; p<m; p++{
        for q:=0; q<n; q++{
            if board[p][q]==wordByte[0] && dfs(p, q, 0){
                return true
            }
        }
    }
    return false
}

提交结果如下

?

?