由于本站访问压力较大
微信扫码关注公众号 labuladong
回复关键词「解锁」
按照操作即可解锁本站全部文章
数据结构精品课 已更新到 V2.1, 手把手刷二叉树系列课程 上线。
LeetCode | 力扣 | 难度 |
---|---|---|
10. Regular Expression Matching | 10. 正则表达式匹配 | 🔴 |
- | 剑指 Offer 19. 正则表达式匹配 | 🔴 |
———–
正则表达式是一个非常强力的工具,本文就来具体看一看正则表达式的底层原理是什么。力扣第 10 题「 正则表达式匹配」就要求我们实现一个简单的正则匹配算法,包括「.」通配符和「*」通配符。
这两个通配符是最常用的,其中点号「.」可以匹配任意一个字符,星号「*」可以让之前的那个字符重复任意次数(包括 0 次)。
比如说模式串 ".a*b"
就可以匹配文本 "zaaab"
,也可以匹配 "cb"
;模式串 "a..b"
可以匹配文本 "amnb"
;而模式串 ".*"
就比较牛逼了,它可以匹配任何文本。
题目会给我们输入两个字符串 s
和 p
,s
代表文本,p
代表模式串,请你判断模式串 p
是否可以匹配文本 s
。我们可以假设模式串只包含小写字母和上述两种通配符且一定合法,不会出现 *a
或者 b**
这种不合法的模式串,
函数签名如下:
// 注意:java 代码由 chatGPT🤖 根据我的 cpp 代码翻译,旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试,仅供参考,如有疑惑,可以参照我写的 cpp 代码对比查看。
boolean isMatch(String s, String p);
bool isMatch(string s, string p);
# 注意:python 代码由 chatGPT🤖 根据我的 cpp 代码翻译,旨在帮助不同背景的读者理解算法逻辑。
# 本代码还未经过力扣测试,仅供参考,如有疑惑,可以参照我写的 cpp 代码对比查看。
def isMatch(s: str, p: str) -> bool:
// 注意:go 代码由 chatGPT🤖 根据我的 cpp 代码翻译,旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试,仅供参考,如有疑惑,可以参照我写的 cpp 代码对比查看。
func isMatch(s string, p string) bool {}
// 注意:javascript 代码由 chatGPT🤖 根据我的 cpp 代码翻译,旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试,仅供参考,如有疑惑,可以参照我写的 cpp 代码对比查看。
var isMatch = function(s, p) {};
对于我们将要实现的这个正则表达式,难点在那里呢?
点号通配符其实很好实现,s
中的任何字符,只要遇到 .
通配符,无脑匹配就完事了。主要是这个星号通配符不好实现,一旦遇到 *
通配符,前面的那个字符可以选择重复一次,可以重复多次,也可以一次都不出现,这该怎么办?
对于这个问题,答案很简单,对于所有可能出现的情况,全部穷举一遍,只要有一种情况可以完成匹配,就认为 p
可以匹配 s
。那么一旦涉及两个字符串的穷举,我们就应该条件反射地想到动态规划的技巧了。
我们先脑补一下,s
和 p
相互匹配的过程大致是,两个指针 i, j
分别在 s
和 p
上移动,如果最后两个指针都能移动到字符串的末尾,那么久匹配成功,反之则匹配失败。
如果不考虑 *
通配符,面对两个待匹配字符 s[i]
和 p[j]
,我们唯一能做的就是看他俩是否匹配:
// 注意:java 代码由 chatGPT🤖 根据我的 cpp 代码翻译,旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试,仅供参考,如有疑惑,可以参照我写的 cpp 代码对比查看。
boolean isMatch(String s, String p) {
int i = 0, j = 0;
while (i < s.length() && j < p.length()) {
// 「.」通配符就是万金油
if (s.charAt(i) == p.charAt(j) || p.charAt(j) == '.') {
// 匹配,接着匹配 s[i+1..] 和 p[j+1..]
i++; j++;
} else {
// 不匹配
return false;
}
}
return i == j;
}
bool isMatch(string s, string p) {
int i = 0, j = 0;
while (i < s.size() && j < p.size()) {
// 「.」通配符就是万金油
if (s[i] == p[j] || p[j] == '.') {
// 匹配,接着匹配 s[i+1..] 和 p[j+1..]
i++; j++;
} else {
// 不匹配
return false;
}
}
return i == j;
}
# 注意:python 代码由 chatGPT🤖 根据我的 cpp 代码翻译,旨在帮助不同背景的读者理解算法逻辑。
# 本代码还未经过力扣测试,仅供参考,如有疑惑,可以参照我写的 cpp 代码对比查看。
def isMatch(s: str, p: str) -> bool:
i, j = 0, 0
while i < len(s) and j < len(p):
# 「.」通配符就是万金油
if s[i] == p[j] or p[j] == '.':
# 匹配,接着匹配 s[i+1..] 和 p[j+1..]
i += 1
j += 1
else:
# 不匹配
return False
return i == j
// 注意:go 代码由 chatGPT🤖 根据我的 cpp 代码翻译,旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试,仅供参考,如有疑惑,可以参照我写的 cpp 代码对比查看。
func isMatch(s string, p string) bool {
i, j := 0, 0
for i < len(s) && j < len(p) {
// 「.」通配符就是万金油
if s[i] == p[j] || p[j] == '.' {
// 匹配,接着匹配 s[i+1..] 和 p[j+1..]
i++
j++
} else {
// 不匹配
return false
}
}
return i == j
}
// 注意:javascript 代码由 chatGPT🤖 根据我的 cpp 代码翻译,旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试,仅供参考,如有疑惑,可以参照我写的 cpp 代码对比查看。
var isMatch = function(s, p) {
let i = 0, j = 0;
while (i < s.length && j < p.length) {
// 「.」通配符就是万金油
if (s[i] === p[j] || p[j] === '.') {
// 匹配,接着匹配 s[i+1..] 和 p[j+1..]
i++; j++;
} else {
// 不匹配
return false;
}
}
return i === j;
};
那么考虑一下,如果加入 *
通配符,局面就会稍微复杂一些,不过只要分情况来分析,也不难理解。
当 p[j + 1]
为 *
通配符时,我们分情况讨论下:
1、如果 s[i] == p[j]
,那么有两种情况:
1.1 p[j]
有可能会匹配多个字符,比如 s = "aaa", p = "a*"
,那么 p[0]
会通过 *
匹配 3 个字符 "a"
。
1.2 p[i]
也有可能匹配 0 个字符,比如 s = "aa", p = "a*aa"
,由于后面的字符可以匹配 s
,所以 p[0]
只能匹配 0 次。
2、如果 s[i] != p[j]
,只有一种情况:
p[j]
只能匹配 0 次,然后看下一个字符是否能和 s[i]
匹配。比如说 s = "aa", p = "b*aa"
,此时 p[0]
只能匹配 0 次。
综上,可以把之前的代码针对 *
通配符进行一下改造:
if (s[i] == p[j] || p[j] == '.') {
// 匹配
if (j < p.size() - 1 && p[j + 1] == '*') {
// 有 * 通配符,可以匹配 0 次或多次
} else {
// 无 * 通配符,老老实实匹配 1 次
i++; j++;
}
} else {
// 不匹配
if (j < p.size() - 1 && p[j + 1] == '*') {
// 有 * 通配符,只能匹配 0 次
} else {
// 无 * 通配符,匹配无法进行下去了
return false;
}
}
整体的思路已经很清晰了,但现在的问题是,遇到 *
通配符时,到底应该匹配 0 次还是匹配多次?多次是几次?
你看,这就是一个做「选择」的问题,要把所有可能的选择都穷举一遍才能得出结果。动态规划算法的核心就是「状态」和「选择」,「状态」无非就是 i
和 j
两个指针的位置,「选择」就是 p[j]
选择匹配几个字符。
根据「状态」,我们可以定义一个 dp
函数:
bool dp(string& s, int i, string& p, int j);
_____________
应合作方要求,本文不便在此发布,请扫码关注回复关键词「正则」或 点这里 查看:
共同维护高质量学习环境,评论礼仪见这里,违者直接拉黑不解释