LeetCode - #10 正则表达式匹配(Top 100)
2023-04-18 12:38:14 时间
前言
本题为 LeetCode 前 100 高频题
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] 练习
往期回顾
已发布的文章中有 5 篇高频题
难度水平:容易,公司面试使用频率如下:
公司 | 频率 |
---|---|
Amazon | ★★★★★★ |
★★★★★ | |
Airbnb | ★★★★★ |
Microsoft | ★★★★★ |
★★★★ |
难度水平:中等,公司面试使用频率如下:
公司 | 频率 |
---|---|
Microsoft | ★★★★ |
Amazon | ★★ |
Airbnb | ★★ |
难度水平:中等,公司面试使用频率如下:
公司 | 频率 |
---|---|
Amazon | ★★ |
难度水平:困难
难度水平:中等,公司面试使用频率如下:
公司 | 频率 |
---|---|
Amazon | ★★ |
难度水平:容易、中等、困难 公司使用频率:1 ~ 6 颗 ★
关于我们
参考资料
[1]
@故胤道长: https://m.weibo.cn/u/1827884772
[2]
LeetCode-Swift: https://github.com/soapyigu/LeetCode-Swift
[3]
LeetCode: https://leetcode.com/problems/regular-expression-matching
相关文章
- 【技术种草】cdn+轻量服务器+hugo=让博客“云原生”一下
- CLB运维&运营最佳实践 ---访问日志大洞察
- vnc方式登陆服务器
- 轻松学排序算法:眼睛直观感受几种常用排序算法
- 十二个经典的大数据项目
- 为什么使用 CDN 内容分发网络?
- 大数据——大数据默认端口号列表
- Weld 1.1.5.Final,JSR-299 的框架
- JavaFX 2012:彻底开源
- 提升as3程序性能的十大要点
- 通过凸面几何学进行独立于边际的在线多类学习
- 利用行动影响的规律性和部分已知的模型进行离线强化学习
- ModelLight:基于模型的交通信号控制的元强化学习
- 浅谈Visual Source Safe项目分支
- 基于先验知识的递归卡尔曼滤波的代理人联合状态和输入估计
- 结合网络结构和非线性恢复来提高声誉评估的性能
- 最佳实践丨云开发CloudBase多环境管理实践
- TimeVAE:用于生成多变量时间序列的变异自动编码器
- 具有线性阈值激活的神经网络:结构和算法
- 内网渗透之横向移动 -- 从域外向域内进行密码喷洒攻击