Leetcode 10 正则表达式匹配
给你一个字符串 和一个字符规律 ,请你来实现一个支持 '.'
和 '*'
的正则表达式匹配。
'.'
匹配任意单个字符;
'*'
匹配零个或多个前面的那一个元素;
所谓匹配,是要涵盖 整个字符串 的,而不是部分字符串。
示例 1
输入:"aa"
"a"
输出:false
解释:"a"
无法匹配 "aa"
整个字符串。
示例 2
输入: "aa"
"a*"
输出:true
解释:因为 '*'
代表可以匹配零个或多个前面的那一个元素, 在这里前面的元素就是 'a'
。因此,字符串 "aa"
可被视为 'a'
重复了一次。
示例 3
输入: "ab"
$p = $".*"
输出:true
解释:".*"
表示可匹配零个或多个('*'
)任意字符('.'
)。
示例 4
输入: "aab"
$p = $"c*a*b"
输出:true
解释:因为 '*'
表示零个或多个,这里 'c'
为 个, 'a'
被重复一次。因此可以匹配字符串 "aab"
。
示例 5
输入: "mississippi"
"mis*is*p*."
输出:false
提示
可能为空,且只包含小写字母。
可能为空,且只包含小写字母,以及字符 '.'
和 '*'
。
保证每次出现字符 *
时,前面都匹配到有效的字符。
思路
默认字符串下标都从 开始,从 开始的都是sb。定义 为 与 匹配的真值。
下标从 开始便于考虑边界条件,两个空字符串匹配,;空字符串与形如a*b*c*...
的字符串也可匹配,即 *
。
最优子结构: 与 匹配,则 与 必能分别分成 段子串,使得 段子串分别匹配。
无后效性:若 与 的匹配方式确定,则此后的匹配只与当前的状态有关。
必为小写字母,我们需要考虑 的字符类型。
-
为小写字母,必须要让 且 与 匹配,才能使得 与 匹配,。
-
为
.
,可以匹配任意字符,只需要 与 匹配,就能使得 与 匹配,。 -
为
*
,有如下两种选择:- 扩展 ,即形成 , 的个数不少于 ;
- 不扩展 ,即 不出现;
- 当 且
.
,只有 不出现才有可能使得 与 匹配上,即 ; - 当 或
.
,可以兼顾上述两种选择;当选择不扩展 ,;当选择扩展 ,;实际上,选择扩展时,匹配的是形如a*
即aaaaaaa...
这样的字符串,若 ,,本质上是匹配了 ,然后将 扔掉,用 继续匹配 ,故 。
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42class Solution {
public:
bool isMatch(string s, string p) {
const int m = s.length(), n = p.length();
s = '\0' + s;
p = '\0' + p;
bool** f = new bool* [m + 1];
for (int i = 0; i <= m; i++) {
f[i] = new bool[n + 1];
memset(f[i], false, sizeof(bool) * (n + 1));
}
f[0][0] = true;
for (int j = 1; j <= n; j++) {
if (j >= 2 && p[j] == '*') {
f[0][j] = f[0][j - 2];
}
}
for (int i = 1; i <= m; i++) {
for (int j = 1; j <= n; j++) {
if (isalpha(p[j])) {
f[i][j] = (s[i] == p[j]) & f[i - 1][j - 1];
} else if (p[j] == '.') {
f[i][j] = f[i - 1][j - 1];
} else {
if (s[i] == p[j - 1] || p[j - 1] == '.') {
f[i][j] = f[i - 1][j];
if (j >= 2) {
f[i][j] |= f[i][j - 2];
}
} else if (j >= 2) {
f[i][j] = f[i][j - 2];
}
}
}
}
bool ans = f[m][n];
for (int i = 0; i <= m; i++) {
delete[]f[i];
}
return ans;
}
};