class Solution {
public:
bool isMatch(string s, string p) {
int n = s.size(), m = p.size();
s = ‘ ‘ + s, p = ‘ ‘ + p;
// vector<vector<bool> > f(n, vector<bool> (m, 0));
vector<vector<bool> > f(n + 10, vector<bool> (m + 10, false));
f[0][0] = true;
for(int i = 0; i <= n; i ++)
for(int j = 1; j <= m; j ++)
{
if(p[j + 1] == '*') continue;
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];
}
};
作者:林业栋
链接:https://www.acwing.com/solution/content/12686/
来源:AcWing
著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。