剑指 Offer 12. 矩阵中的路径

题目描述

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

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

题目同leetcode 70.word-search

题解

DFS解法

func exist(board [][]byte, word string) bool {
    for row := 0; row < len(board); row ++{
        for col := 0;col < len(board[row]); col ++{
            if dfs(board, word, row, col, 0) {
                return true
            }
        }
    }
    return false
}

func dfs(board [][]byte, word string, i, j, idx int) bool {
    //越界或者字符不相等
    if i < 0 || i >= len(board) || 
    j < 0 || j >= len(board[0]) || 
    board[i][j] != word[idx] {
        return false
    }

    if idx == len(word) - 1 {
        return true
    }

    //标记已被访问
    tmpCh := board[i][j]
    board[i][j] = '/'

    //上下左右检查一下
    check := (dfs(board, word, i+1, j, idx+1) || dfs(board, word, i-1, j, idx + 1) || 
    dfs(board, word, i, j+1, idx+1) || dfs(board, word, i, j-1, idx+1))

    //恢复
    board[i][j] = tmpCh
    return check
}