递归法
class Solution {
int[][] f;
public boolean isMatch(String s, String p) {
f = new int[s.length() + 1][p.length() + 1];
for (int i = 0; i < f.length; i++) {
for (int j = 0; j < f[i].length; j++) {
f[i][j] = -1;
}
}
return isMatch(s, p, 0, 0);
}
private boolean isMatch(String s, String p, int x, int y) {
// 使用f[][]二维数组进行记忆优化
if (f[x][y] != -1) {
return f[x][y] != 0;
}
if (y == p.length()) {
f[x][y] = x;
return x == s.length();
}
boolean res;
if (p.charAt(y) == '*') {
// 如果p[j]是通配符'*'，则，下面的情况只要有一种满足，f[i][j]就是真；
// 在满足x < s.length()的前提下, f[i + 1][j]是真；
// f[i][j + 1]是真；
res = x < s.length() && isMatch(s, p, x + 1, y) || isMatch(s, p, x, y + 1);
} else {
// 如果p[j]不是通配符'*'，则在满足x < s.length()的前提下, f[i][j]是真，当且仅当s[i]可以和p[j]匹配，且f[i+1][j+1]是真；
res = x < s.length() && (s.charAt(x) == p.charAt(y) || p.charAt(y) == '?') && isMatch(s, p, x + 1, y + 1);
}
f[x][y] = res ? 1 : 0;
return res;
}
}
- 时间复杂度 O(mn)，n 表示 s 的长度，m 表示p的长度
- 空间复杂度 O(mn)，n 表示 s 的长度，m 表示p的长度
迭代法
class Solution {
public boolean isMatch(String s, String p) {
int n = s.length();
int m = p.length();
boolean[][] f = new boolean[n + 1][m + 1];
f[0][0] = true;
// 特殊情况， p为形如“**a”这种以"*"开头的
for (int i = 1; i <= m; i++) {
if (p.charAt(i - 1) == '*') {
f[0][i] = true;
} else {
break;
}
}
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
if (p.charAt(j - 1) == '*') {
f[i][j] = f[i][j - 1] || f[i - 1][j];
} else if (p.charAt(j - 1) == '?' || s.charAt(i - 1) == p.charAt(j - 1)) {
f[i][j] = f[i - 1][j - 1];
}
}
}
return f[n][m];
}
}
- 时间复杂度 O(mn)，n 表示 s 的长度，m 表示p的长度
- 空间复杂度 O(mn)，n 表示 s 的长度，m 表示p的长度
