class Solution {
public:
/**
* 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
*
*
* @param str string字符串
* @param pattern string字符串
* @return bool布尔型
*/
bool match(string str, string pattern) {
// write code here
int n = str.size();
int m = pattern.size();
vector<vector<bool>> f(n+1, vector<bool>(m+1, false)); // f[i][j]代表str前i个和pattern前j个匹配情况
// 初始化
f[0][0] = true;
for(int i = 0; i <= n; i++) {
for(int j = 0; j <= m; j++) {
if(j != 0){
if(pattern[j - 1] != '*') {
if(i > 0 && (str[i-1] == pattern[j-1] || pattern[j-1] == '.'))
f[i][j] = f[i-1][j-1];
} else {
// if(f[i][j-1]) // 星号匹配一次
// f[i][j] = f[i][j-1];
if(j >= 2 && f[i][j-2]) // 星号匹配零次
f[i][j] = f[i][j-2];
else if(i >= 1 && j >= 2) // 星号匹配多次
f[i][j] = (f[i-1][j] && (str[i-1] == pattern[j-2] || pattern[j-2] == '.'));
}
}
}
}
return f[n][m];
}
};