题解 | #正则表达式匹配#
正则表达式匹配
https://www.nowcoder.com/practice/28970c15befb4ff3a264189087b99ad4
class Solution {
public:
/*
把能确定的都确定下来,(能确定的一般都是只能满足一种迭代方程的,或者不再迭代方程定义域内的)
*/
bool match(string str, string pat) {
int n = str.size(), m = pat.size();
vector<vector<bool>> dp(n+1,vector<bool>(m+1,false));
dp[0][0] = true;
for(int j = 2; j <= m; j++){
// 当 str 为空串时,只能是0次
if(pat[j-1] == '*') dp[0][j] = dp[0][j-2];
}
for(int i = 1; i <= n; i++){
for(int j = 1; j <= m; j++){
if(pat[j-1] == '.' || pat[j-1] == str[i-1]){
dp[i][j] = dp[i-1][j-1];
}else if(j >= 2 && pat[j-1] == '*'){
if(pat[j-2] == '.' || str[i-1] == pat[j-2]){
// 能进行匹配可有 0 次 1 次 或 多次!
dp[i][j] = dp[i][j-2] || dp[i-1][j-2] || dp[i-1][j];
}else {
// 不匹配,只能是 0 次!
dp[i][j] = dp[i][j-2];
}
}
}
}
return dp[n][m];
}
};
