题目
题目链接
题解
动态规划解法：
class Solution {
public boolean isMatch(String s, String p) {
// 状态保存 大小 (s.len + 1) * (p.len + 1)
// 含义 dp[i][j] 为 p(0..i) 与 s(0..j) 是否匹配 p(0..i) 与 s(0..j) 分别为p和s的子串
boolean[][] dp = new boolean[p.length() + 1][s.length() + 1];
for (int i = 0; i <= p.length(); i++) {
for (int j = 0; j <= s.length(); j++) {
// 边界处理
if (i == 0 && j == 0) {
dp[i][j] = true;
continue;
} else if (i == 0 && j != 0) {
dp[i][j] = false;
continue;
} else if (i != 0 && j == 0) {
dp[i][j] = dp[i - 1][j] && p.charAt(i - 1) == '*';
continue;
}
// 转移方程
if (p.charAt(i - 1) == '*') {
dp[i][j] = dp[i][j - 1] || dp[i - 1][j];
} else if (p.charAt(i - 1) == '?') {
dp[i][j] = dp[i - 1][j - 1];
} else {
dp[i][j] = dp[i - 1][j - 1] && s.charAt(j - 1) == p.charAt(i - 1);
}
}
}
return dp[p.length()][s.length()];
}
}