当前位置：首页 > news >正文

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

news 2025/5/30 14:45:08

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

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

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

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

🧩 问题描述

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

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

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

🧠 解题思路

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

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

我们使用一个二维布尔数组 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.countvar 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]
}

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

指标	复杂度
时间复杂度	O(m × n)
空间复杂度	O(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，但题目要求自己实现匹配逻辑，不能用现成库。

✅ 总结

方法	时间复杂度	空间复杂度	是否推荐
递归	O(2^(m+n))	O(m+n)	❌
动态规划	O(m × n)	O(m × n)	✅
动态规划（优化）	O(m × n)	O(n)	✅ （进阶）
正则库调用	—	—	❌（不符合题意）