1.递归求解up to bottom, 从(0, 0)开始递归求解到(m, n)= true, 再回到(0,0)
class Solution {
public boolean isMatch(String s, String p) {
return isMatch(s, 0, p, 0); //从p[j]开始到结尾,是否匹配s[i]到结尾
}
private boolean isMatch(String s, int i, String p, int j) {
if (j >= p.length()) {
return i == s.length();
}
boolean charMatch = (i < s.length()) && (s.charAt(i) == p.charAt(j) || p.charAt(j) == '.'); // s[i] == p[j]
if (j + 1 < p.length() && p.charAt(j + 1) == '*') {
// p[j + 1] == '*',
// 匹配0个p[j], 跳过p[j],p[j+1], p[i]不动
// 匹配多个p[j], 前提s[i] == p[j],跳过s[i],p[j]不变,可以继续和s[i+1]匹配
return isMatch(s, i, p, j + 2) || (charMatch && isMatch(s, i + 1, p, j));
} else {
// p[j + 1] != '*', 如果 s[i] == p[j], 同时跳过s[i]和p[j]
return charMatch && isMatch(s, i + 1, p, j + 1);
}
}
}
2.递归+记忆
class Solution {
public boolean isMatch(String s, String p) {
int m = s.length();
int n = p.length();
Boolean[][] dp = new Boolean[m+1][n+1];
return match(s, 0, p, 0, dp);
}
private boolean match(String s, int i, String p, int j, Boolean[][] dp) {
if (dp[i][j] != null) {
return dp[i][j];
}
if (j == p.length()) {
dp[i][j] = i == s.length();
return dp[i][j];
}
boolean charMatch = (i < s.length()) && (s.charAt(i) == p.charAt(j) || p.charAt(j) == '.');
if (j + 1 < p.length() && p.charAt(j + 1) == '*') {
dp[i][j] = match(s, i, p, j + 2, dp) || (charMatch && match(s, i + 1, p, j, dp));
} else {
dp[i][j] = charMatch && match(s, i + 1, p, j + 1, dp);
}
return dp[i][j];
}
}
3.dp,从bottom to up。dp[0][0] = true开始,求出dp[m][n]
class Solution {
public boolean isMatch(String s, String p) {
int m = s.length();
int n = p.length();
boolean[][] dp = new boolean[m+1][n+1]; // dp[i][j]表示s中[0...i-1]和p中[0...j-1]是否匹配
dp[0][0] = true;
char[] ss = s.toCharArray();
char[] pp = p.toCharArray();
for (int i = 0; i <= m; i ++) {
for (int j = 1; j <= n; j ++) {
//检查当前字符ss[i-1],pp[j-1]
if (pp[j-1] != '*') {
if (i > 0 && (ss[i-1] == pp[j-1] || pp[j-1] == '.')) {
dp[i][j] = dp[i-1][j-1];
}
} else {
// pp[j-1] == '*'
if (j >= 2)
dp[i][j] = dp[i][j] || dp[i][j-2];
if (i >= 1 && j >= 2 && (ss[i-1] == pp[j-2] || pp[j-2] == '.')) {
dp[i][j] = dp[i][j] || dp[i-1][j];
}
}
}
}
return dp[m][n];
}
}