题目描述
给你一个字符串s
和一个字符规律p
,请你来实现一个支持 .
和 *
的正则表达式匹配。
.
匹配任意单个字符
*
匹配零个或多个前面的那一个元素
所谓匹配,是要涵盖整个字符串s
的,而不是部分字符串。
样例
输入:s = "ab", p = ".*"
输出:true
解释:".*" 表示可匹配零个或多个('*')任意字符('.')。
算法1
(DP) $O(n^2)$
C++ 代码
class Solution {
public:
bool isMatch(string s, string p) {
int n = s.size() , m = p.size();
vector<vector<bool>> f(n+1,vector<bool>(m + 1));
s = ' ' + s , p =' ' + p;
f[0][0] = true;
for(int i = 0;i <= n; i ++)
for(int j = 1;j <= m ; j ++){
if(j + 1 < m && p[j + 1] == '*') continue;
//在这里我们将类似与 a*的当做一个整体,所以在这里计算的时候选择先跳过
else if(i && p[j] != '*')f[i][j] = f[i-1][j-1] && (s[i] == p[j] || p[j] =='.');
else if(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];
}
};