|
?题目来源：正则表达式匹配_牛客题霸_牛客网
描述
请实现一个函数用来匹配包括'.'和'*'的正则表达式。
1.模式中的字符'.'表示任意一个字符
2.模式中的字符'*'表示它前面的字符可以出现任意次（包含0次）。?
在本题中，匹配是指字符串的所有字符匹配整个模式。例如，字符串"aaa"与模式"a.a"和"ab*ac*a"匹配，但是与"aa.a"和"ab*a"均不匹配
数据范围:
1.str 只包含从?a-z?的小写字母。
2.pattern 只包含从?a-z?的小写字母以及字符?.?和?*，无连续的?'*'。
3. 1≤str.length≤1000?
4.?1≤pattern.length≤1000?
代码：
采用
class Solution {
public:
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param str string字符串
* @param pattern string字符串
* @return bool布尔型
*/
bool isMatch(string str, string pattern, int i, int j){
if(pattern[j-1] == '.')
return true;
return pattern[j-1] == str[i-1];
}
bool match(string str, string pattern) {
// write code here
int m = str.length(); //str的长度
int n = pattern.length();
vector<vector<bool>> f(m+1,vector<bool>(n+1,false));
f[0][0]=true;
for(int j = 2; j <= n; j ++){ //i从0开始，因为'a*'这种情况，可以匹配空串
if(pattern[j - 1] == '*') f[0][j] = f[0][j - 2];
}
for(int i=1;i<=m;i++){//str
for(int j=1;j<=n;j++){//pattern
if(pattern[j-1] == '*'){
f[i][j] = f[i][j] | f[i][j-2];
if(isMatch(str , pattern , i , j-1)){//如果pattern的上一个字符和str当前字符一致
f[i][j] = f[i][j] | f[i-1][j];//取或运算，如果有序列可以为true则保存true值
}
}
else{
if(isMatch(str , pattern , i , j))//如果当前字符不是'*'
f[i][j] = f[i][j] | f[i-1][j-1];
}
}
}
return f[m][n];
}
};
?
|