链接
https://leetcode-cn.com/problems/regular-expression-matching/
题意
给你一个 匹配串 s 和一个 模式串 p,实现一个支持 ‘.’ 和 ‘*’ 的正则表达式匹配。
’.’ 匹配任意单个字符
’*’ 匹配零个或多个前面的那一个元素
思路
动态规划。
d
p
[
i
]
[
j
]
dp[i][j]
dp[i][j] 表示
s
[
i
:
]
s[i:]
s[i:] 和
p
[
j
:
]
p[j:]
p[j:] 是否能匹配。自底向上计算。
因为有 ‘*’,’*’ 比较麻烦,它会出现在当前匹配的字符的后面,匹配零个或任意多个当前元素。也就是说可以有 任意多个 当前字符,也可以 没有(忽略)。
[
0
,
∞
)
[0, \infty)
[0,∞)
分两种情况讨论:
f
i
r
s
t
_
m
a
t
c
h
=
(
s
[
i
]
=
=
p
[
j
]
或
者
p
[
j
]
=
=
′
.
′
)
(
当
前
字
符
是
否
匹
配
)
first\_match = (s[i] == p[j] 或者 p[j] == '.') (当前字符是否匹配)
first_match=(s[i]==p[j]或者p[j]==′.′)(当前字符是否匹配)
- 当前字符后面是 ‘*’ 的情况,
if(j+1 < p.size() && p[j+1] == '*')
,可以有两种选择,忽略 模式串p 的这个字符(0个),或者在匹配当前字符的情况下 模式串p不动 继续匹配剩下的 匹配串s(任意多个)。
d
p
[
i
]
[
j
]
=
{
d
p
[
i
]
[
j
+
2
]
(
0
个
)
f
i
r
s
t
_
m
a
t
c
h
&
&
d
p
[
i
+
1
]
[
j
]
(
任
意
多
个
)
dp[i][j] = \begin{cases} dp[i][j+2] \ \ (0个) \\ first\_match \ \&\&\ dp[i+1][j] \ \ (任意多个) \end{cases}
dp[i][j]={dp[i][j+2] (0个)first_match && dp[i+1][j] (任意多个) - 没有 ‘*’ 的情况,直接匹配当前字符和剩下的串即可:
d
p
[
i
]
[
j
]
=
f
i
r
s
t
_
m
a
t
c
h
&
&
d
p
[
i
+
1
]
[
j
+
1
]
dp[i][j] = first\_match \ \&\&\ dp[i+1][j+1]
dp[i][j]=first_match && dp[i+1][j+1]
PS: 初始化时需要注意
j == p.size()
相当于 模式串 p 为空,只要 匹配串 s 不为空,一定匹配失败。
d
p
[
i
]
[
p
.
s
i
z
e
(
)
]
=
0
dp[i][p.size()] = 0
dp[i][p.size()]=0i== s.size()
相当于 匹配串 s 为空,这时 模式串p 可以不为空而匹配成功,eg:s = "", p = "a*"
。- 模式串p 和 匹配串s 都为 空 是匹配成功的。
d
p
[
s
.
s
i
z
e
(
)
]
[
p
.
s
i
z
e
(
)
]
=
1
dp[s.size()][p.size()] = 1
dp[s.size()][p.size()]=1
AC代码
class Solution {
public:
bool isMatch(string s, string p) {
bool dp[s.size()+1][p.size()+1];
for(int i = 0; i < s.size(); ++i) dp[i][p.size()] = 0;
dp[s.size()][p.size()] = 1;
for(int i = s.size(); i >= 0; --i) {
for(int j = p.size()-1; j >= 0; --j) {
bool first_match = i < s.size() && (s[i] == p[j] || p[j] == '.');
if(j+1 < p.size() && p[j+1] == '*') {
dp[i][j] = dp[i][j+2] || (first_match && dp[i+1][j]);
}
else {
dp[i][j] = first_match && dp[i+1][j+1];
}
}
}
return dp[0][0];
}
};
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)