AcWing 30. 正则表达式匹配
原题链接
困难
作者:
我要出去乱说
,
2021-02-05 00:22:48
,
所有人可见
,
阅读 567
class Solution {
public:
bool isMatch(string s, string p) {
int n = s.size(), m = p.size();
s = ' ' + s, p = ' ' + p; //为了让字符串从1开始,前面补一个空格
vector<vector<bool>> f(n + 1, vector<bool>(m + 1)); //定义状态数组,补了空格,长度相应加1
f[0][0] = true; //f[i][j]=true 表示前i个字符串与前j个模式串是匹配的
//i要从0开始枚举,因为可能出现s为空p为"a*"的情况
for (int i = 0; i <= n; i ++ )
for (int j = 1; j <= m; j ++ )
{
if (j + 1 < m && p[j + 1] == '*') continue;
if (i && p[j] != '*')
{
//s和p通过字符或'.'匹配的情况
f[i][j] = f[i - 1][j - 1] && (s[i] == p[j] || p[j] == '.');
}
else if (p[j] == '*')
{
//后一个条件已经判断i>0了,f[i][j-2]用来特判s为空且p为"a*"模式的情况,即f[0][0]=true
//f[i-1][j]表示s上一个字符匹配到p的j时是否为真,只有上一个时为真,这次加上*号才能也为真
f[i][j] = f[i][j - 2] || i && f[i - 1][j] && (s[i] == p[j - 1] || p[j - 1] == '.');
}
}
return f[n][m];
}
};