LeetCode - #79 单词搜索（Top 100）

前言

本题为 LeetCode 前 100 高频题

我们社区陆续会将顾毅（Netflix 增长黑客，《iOS 面试之道》作者，ACE 职业健身教练。）的 Swift 算法题题解整理为文字版以方便大家学习与阅读。

LeetCode 算法到目前我们已经更新了 78 期，我们会保持更新时间和进度（周一、周三、周五早上 9:00 发布），每期的内容不多，我们希望大家可以在上班路上阅读，长久积累会有很大提升。

不积跬步，无以至千里；不积小流，无以成江海，Swift社区 伴你前行。如果大家有建议和意见欢迎在文末留言，我们会尽力满足大家的需求。

难度水平：中等

1. 描述

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

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

2. 示例

示例 1

输入：board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCCED"
输出：true

示例 2

输入：board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "SEE"
输出：true

示例 3

输入：board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCB"
输出：false

约束条件：

• m == board.length
• n = board[i].length
• 1 <= m, n <= 6
• 1 <= word.length <= 15
• board 和 word 仅由大小写英文字母组成

3. 答案

class WordSearch {
    func exist(board: [[Character]], _ word: String) -> Bool {
        guard board.count > 0 && board[0].count > 0 else {
            return false
        }
        
        let m = board.count
        let n = board[0].count
        var visited = Array(count: m, repeatedValue: Array(count: n, repeatedValue: false))
        var wordContent = [Character](word.characters)
        
        for i in 0..<m {
            for j in 0..<n {
                if board[i][j] == wordContent[0] && _dfs(board, wordContent, m, n, i, j, &visited, 0) {
                    return true
                }
            }
        }
        
        return false
    }
    
    private func _dfs(board: [[Character]], _ wordContent: [Character], _ m: Int, _ n: Int, _ i: Int, _ j: Int, inout _ visited: [[Bool]], _ index: Int) -> Bool {
        if index == wordContent.count {
            return true
        }
    
        guard i >= 0 && i < m && j >= 0 && j < n else {
            return false
        }
        guard !visited[i][j] && board[i][j] == wordContent[index] else {
            return false
        }
        
        visited[i][j] = true
        
        if _dfs(board, wordContent, m, n, i + 1, j, &visited, index + 1) || _dfs(board, wordContent, m, n, i - 1, j, &visited, index + 1) || _dfs(board, wordContent, m, n, i, j + 1, &visited, index + 1) || _dfs(board, wordContent, m, n, i, j - 1, &visited, index + 1) {
            return true
        }
        visited[i][j] = false
        
        return false
    }
}

• 主要思想：经典深度优先搜索，上，下，左，右四个方向。
• 时间复杂度： O(mn * 4^(k - 1))， m和n分别代表矩阵的宽和高，k为单词大小
• 空间复杂度： O(mn)

该算法题解的仓库：LeetCode-Swift

点击前往 LeetCode 练习

关于我们

我们是由 Swift 爱好者共同维护，我们会分享以 Swift 实战、SwiftUI、Swift 基础为核心的技术内容，也整理收集优秀的学习资料。

后续还会翻译大量资料到我们公众号，有感兴趣的朋友，可以加入我们。