1愈腾、題目
image.png
2泄鹏、分析
遞歸(https://labuladong.github.io/zgnb/3/17/30/)：
if (s[i] == p[j] || p[j] == '.') {
// 匹配
if (j < p.size() - 1 && p[j + 1] == '*') {
// 有 * 通配符，可以匹配 0 次或多次
} else {
// 無 * 通配符现横，老老實(shí)實(shí)匹配 1 次
i++; j++;
}
} else {
// 不匹配
if (j < p.size() - 1 && p[j + 1] == '*') {
// 有 * 通配符，只能匹配 0 次
} else {
// 無 * 通配符，匹配無法進(jìn)行下去了
return false;
}
}
動態(tài)規(guī)劃：
3舍悯、代碼
class Solution {
int NO_USE = -1;
int TRUE = 1;
int FALSE = 0;
public boolean isMatch(String s, String p) {
int[][] memo = new int[s.length()][p.length()];
for(int i = 0; i < s.length(); i++){
Arrays.fill(memo[i], NO_USE);
}
int res = dp(s, 0, p, 0, memo);
return res == FALSE ? false : true;
}
private int dp(String s, int i, String p, int j, int[][] memo){
int m = s.length();
int n = p.length();
if(i >= m){
if((n - j) % 2 != 0) return FALSE;
int pRes = TRUE;
for(int k = j; k < n; k+=2){
if(p.charAt(k + 1) != '*') pRes = FALSE;
}
return pRes;
}
if(j >= n){
if(i == m) return TRUE;
return FALSE;
}
if(memo[i][j] != NO_USE) return memo[i][j];
if(s.charAt(i) == p.charAt(j) || p.charAt(j) == '.'){
if(j + 1 < n && p.charAt(j + 1) == '*'){
if(dp(s, i, p, j + 2, memo) == TRUE
|| dp(s, i + 1, p, j, memo) == TRUE){
memo[i][j] = TRUE;
}
else{
memo[i][j] = FALSE;
}
return memo[i][j];
}
memo[i][j] = dp(s, i + 1, p, j + 1, memo);
}else{
if(j + 1 < n && p.charAt(j + 1) == '*'){
memo[i][j] = dp(s, i, p, j + 2, memo);
return memo[i][j];
}
memo[i][j] = FALSE;
}
return memo[i][j];
}
}
