LeetCode 44. Wildcard Matching
原题链接
简单
作者:
邓泽军
,
2019-09-10 16:10:50
,
所有人可见
,
阅读 900
C++ 代码
class Solution {
public:
int n, m;
vector<vector<int>> f;
bool isMatch(string s, string p) {
n = s.size(), m = p.size();
f = vector<vector<int>>(n + 1, vector<int>(m + 1, -1));
return dfs(s, p, 0, 0);
}
bool dfs(string &s, string &p, int x, int y) {
if (f[x][y] != -1) return f[x][y];
if (y == m) return f[x][y] = x == n;
bool ans;
if (p[y] == '*')
ans = x < n && dfs(s, p, x + 1, y) || dfs(s, p, x, y + 1);
else if (x < n && (s[x] == p[y] || p[y] == '?')){
ans = dfs(s, p, x + 1, y + 1);
}
else ans = false;
return f[x][y] = ans;
}
};