每日算法 -【Swift 算法】正则表达式匹配：支持 `.` 和 `*`

🚀 用动态规划实现正则表达式匹配：支持 . 和 *

在这篇文章中，我们将深入探讨如何实现一个正则表达式匹配引擎，支持两个基础通配符：

• .：匹配任意一个字符
• *：匹配零个或多个前面的字符

该问题是 LeetCode 上的经典题目，也常出现在算法面试中。我们将重点分析动态规划的解法，比较不同方法的优劣，并分析时间复杂度与空间复杂度。

🧩 问题描述

给定一个字符串 s 和一个字符模式 p，实现一个函数来匹配它们。支持以下规则：

• . 匹配任意一个字符；
• * 匹配零个或多个前面的字符。

⚠️ 注意：匹配必须覆盖整个字符串，而不是部分匹配。

🧠 解题思路

这是一个典型的动态规划（DP）问题，满足：

1. 最优子结构：一个大问题的解可以通过子问题的解推导出来。
2. 子问题重叠：很多状态会重复出现，比如重复处理同样前缀。
3. 无后效性：状态转移只依赖当前状态，不依赖“历史路径”。

我们使用一个二维布尔数组 dp[i][j] 来表示：

字符串 s 的前 i 个字符 s[0..<i] 是否匹配模式 p 的前 j 个字符 p[0..<j]

✅ 动态规划解法（Swift 实现）

func isMatch(_ s: String, _ p: String) -> Bool {
    let sChars = Array(s), pChars = Array(p)
    let m = sChars.count, n = pChars.count
    var dp = Array(repeating: Array(repeating: false, count: n + 1), count: m + 1)
    dp[0][0] = true  // 空串匹配空模式
    
    // 初始化：空串与形如 a*, a*b*, a*b*c* 这样的模式匹配
    for j in 1...n {
        if pChars[j - 1] == "*" && j >= 2 {
            dp[0][j] = dp[0][j - 2]
        }
    }
    
    for i in 1...m {
        for j in 1...n {
            if pChars[j - 1] == "." || pChars[j - 1] == sChars[i - 1] {
                dp[i][j] = dp[i - 1][j - 1]
            } else if pChars[j - 1] == "*" {
                // 1. 看作前一个字符重复0次
                dp[i][j] = dp[i][j - 2]
                // 2. 看作前一个字符重复 >=1 次
                if pChars[j - 2] == "." || pChars[j - 2] == sChars[i - 1] {
                    dp[i][j] = dp[i][j] || dp[i - 1][j]
                }
            }
        }
    }
    
    return dp[m][n]
}

🧮 时间复杂度与空间复杂度

其中 m 是字符串 s 的长度，n 是模式 p 的长度。我们用一个二维数组记录了所有子状态。

可以进一步优化空间复杂度为 O(n) 使用滚动数组（只保留前一行），但实现会复杂一些。

🧪 示例

isMatch("aa", "a")          // false
isMatch("aa", "a*")         // true
isMatch("ab", ".*")         // true
isMatch("aab", "c*a*b")     // true
isMatch("mississippi", "mis*is*p*.") // false

🚫 其他方法对比

1. 递归（暴力法）

思路：每遇到 * 时考虑多个递归分支。简单直观，但效率低。

func isMatch(_ s: String, _ p: String) -> Bool {
    if p.isEmpty { return s.isEmpty }
    
    let firstMatch = !s.isEmpty && (s.first == p.first || p.first == ".")
    
    if p.count >= 2 && p[p.index(p.startIndex, offsetBy: 1)] == "*" {
        return isMatch(s, String(p.dropFirst(2))) || 
               (firstMatch && isMatch(String(s.dropFirst()), p))
    } else {
        return firstMatch && isMatch(String(s.dropFirst()), String(p.dropFirst()))
    }
}

• ✅ 简洁，但容易爆栈
• ❌ 时间复杂度指数级 O(2^(m+n))

2. 正则表达式库（逃避法）

Swift 提供了 NSRegularExpression，但题目要求自己实现匹配逻辑，不能用现成库。

✅ 总结

📌 总结一句话

动态规划是解决字符串匹配类问题最稳定的武器，核心在于定义合理的状态和转移关系，写对了就赢了！

如果你喜欢这类算法解析，欢迎点赞、评论或收藏支持 👏