Word Search

题目介绍

LeetCode 79. Word Search。

复杂度

时间复杂度: O(3KMN), 空间复杂度: O(k)

解题思路

class Solution {
    var board: [[Character]] = []
    var word: String = ""
    func exist(_ board: [[Character]], _ word: String) -> Bool {
        self.board = board
        self.word  = word
        for i in 0..<board.count {
            for j in 0..<board[0].count {
                if dfs(i, j, 0) {
                    return true
                }
            }
        }
        return false
    }

    func dfs(_ i: Int, _ j: Int, _ k: Int) -> Bool {
        // 终止条件 返回 false
        // ① 行或列索引越界 或 ② 当前矩阵元素与目标字符不同 或 ③ 当前矩阵元素已访问过
        if i < 0 || i >= board.count || j < 0 || j >= board[0].count || board[i][j] != Array(word)[k] {
            return false
        }
        // 终止条件 返回 true
        // 字符串 word 已全部匹配，即 k = word.count - 1 。
        if k == word.count - 1 {
            return true
        }
        // 标记当前矩阵元素
        // 将 board[i][j] 值暂存于变量 tmp ，并修改为字符 '#' ，代表此元素已访问过，防止之后搜索时重复访问。
        let temp = board[i][j]
        board[i][j] = "#"
        // 搜索下一单元格
        // 朝当前元素的 上、下、左、右 四个方向开启下层递归，使用 或 连接 （代表只需一条可行路径） ，并记录结果至 res 。
        let res = dfs(i + 1, j, k + 1) || dfs(i, j + 1, k + 1) || dfs(i, j - 1, k + 1) || dfs(i - 1, j, k + 1)
        // 还原当前矩阵元素
        // 将 tmp 暂存值还原至 board[i][j] 元素。
        board[i][j] = temp
        return res
    }
}

**版权声明**

Ivan’s Blog by Ivan Ye is licensed under a Creative Commons BY-NC-ND 4.0 International License.
由叶帆创作并维护的叶帆的博客博客采用创作共用保留署名-非商业-禁止演绎4.0国际许可证。

本文首发于Ivan’s Blog | 叶帆的博客博客（ http://yeziahehe.com ），版权所有，侵权必究。

本文链接：http://yeziahehe.com/2020/06/26/WordSearch/