您现在的位置是：亿华云 > 应用开发

LeetCode之正则表达式匹配（Top 100）

亿华云2025-10-03 02:11:36【应用开发】6人已围观

简介前言本题为 LeetCode 前 100 高频题我们社区陆续会将顾毅(Netflix 增长黑客，《iOS 面试之道》作者，ACE 职业健身教练。微博:@故胤道长[1])的 Swift 算法题题解整理为

前言

本题为 LeetCode 前 100 高频题

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

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

不积跬步，匹配无以至千里;不积小流，正则表无以成江海，达式Swift社区伴你前行。服务器租用匹配

难度水平：困难

1. 描述

已知一个字符串 s 和一个字符规律 p，请你来实现一个支持 . 和 * 的正则表达式匹配。

. 匹配任意单个字符 * 匹配零个或多个前面的那一个元素

所谓匹配，是要涵盖整个字符串 s 的，而不是部分字符串。

2. 示例

示例 1

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

示例 2

输入：s = "aa" p = "a*" 输出：true 解释：因为 * 代表可以匹配零个或多个前面的那一个元素, 在这里前面的元素就是 a。因此，亿华云计算字符串 "aa" 可被视为 a 重复了一次。

示例 3

输入：s = "ab" p = ".*" 输出：true 解释：".*" 表示可匹配零个或多个（*）任意字符（.）。

示例 4

输入：s = "aab" p = "c*a*b" 输出：true 解释：因为 * 表示零个或多个，这里 c 为 0 个, a 被重复一次。因此可以匹配字符串 "aab"。

示例 5

输入：s = "mississippi" p = "mis*is*p*." 输出：false

约束条件：

1 <= s.length <= 20 1 <= p.length <= 30 s 可能为空，且只包含从 a-z 的小写字母。 p 可能为空，且只包含从 a-z 的小写字母，以及字符 . 和 *。保证每次出现字符 * 时，前面都匹配到有效的字符

3. 答案

class RegularExpressionMatching { func isMatch(_ s: String, _ p: String) -> Bool { let sChars = Array(s), pChars = Array(p) var dp = Array(repeating: Array(repeating: false, count: pChars.count + 1), count: sChars.count + 1) dp[0][0] = true for i in 0...pChars.count { // jump over "" vs. "x*" case dp[0][i] = i == 0 || i > 1 && dp[0][i - 2] && pChars[i - 1] == "*" } for i in 0...sChars.count { for j in 0...pChars.count { guard j > 0 else { continue } let pCurrent = pChars[j - 1] if pCurrent != "*" { dp[i][j] = i > 0 && dp[i - 1][j - 1] && (pCurrent == "." || pCurrent == sChars[i - 1]) } else { dp[i][j] = dp[i][j - 2] || i > 0 && j > 1 && (sChars[i - 1] == pChars[j - 2] || pChars[j - 2] == ".") && dp[i - 1][j] } } } return dp[sChars.count][pChars.count] } } 主要思想：经典二维动态规划时间复杂度： O(mn) 空间复杂度： O(mn)

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

前往 LeetCode[3] 练习