LeetCode - 44 通配符匹配

前言

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

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

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

难度水平：困难

1. 描述

给定一个字符串 (s) 和一个字符模式 (p) ，实现一个支持 '?' 和 '*' 的通配符匹配。

‘?’ 可以匹配任何单个字符。

‘*’ 可以匹配任意字符串（包括空字符串）。

两个字符串完全匹配才算匹配成功。

说明:

s 可能为空，且只包含从 a-z 的小写字母。
p 可能为空，且只包含从 a-z 的小写字母，以及字符 ? 和 *。

2. 示例

示例 1

输入:
s = "aa"
p = "a"
输出: false
解释: "a" 无法匹配 "aa" 整个字符串。

示例 2

输入:
s = "aa"
p = "*"
输出: true
解释: '*' 可以匹配任意字符串。

示例 3

输入:
s = "cb"
p = "?a"
输出: false
解释: '?' 可以匹配 'c', 但第二个 'a' 无法匹配 'b'。

示例 4

输入:
s = "adceb"
p = "*a*b"
输出: true
解释: 第一个 '*' 可以匹配空字符串, 第二个 '*' 可以匹配字符串 "dce".

示例 5

输入:
s = "acdcb"
p = "a*c?b"
输出: false

3. 答案

class WildcardMatching {
    func isMatch(_ s: String, _ p: String) -> Bool {
        let sChars = Array(s), pChars = Array(p)
        var dp = Array(repeating: Array(repeating: false, count: p.count + 1), count: s.count + 1)
        dp[0][0] = true
        
        // must start from 0, to make range feasible and handle empty vs. * case
        for i in 0...s.count {
            for j in 0...p.count {
                guard j > 0 else {
                    continue
                }
                
                let pCurrent = pChars[j - 1]
    
                if pCurrent != "*" {
                    dp[i][j] = i > 0 && dp[i - 1][j - 1] && (pCurrent == sChars[i - 1] || pCurrent == "?")
                } else {
                	// Two situations:
                    // (1) '*' is the first character in p;
                    // (2) For k>=0 and k<=i, there is some dp[k][j-1] being true;
                    //     and '*' will match the rest sequence in s after index k;
                    var flag = false
                    for k in 0...i {
                        if dp[k][j - 1] {
                            flag = true
                            break
                        }
                    }
                    
                    dp[i][j] = flag || j == 1   
                }
            }
        }
        
        return dp[s.count][p.count]
    }
}

主要思想：经典的二维动态规划。
时间复杂度： O(mn)
空间复杂度： O(mn)

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

点击前往 LeetCode 练习

关于我们

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

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