-
If p.charAt(j) == s.charAt(i) : dp[i][j] = dp[i-1][j-1];
-
If p.charAt(j) == ‘.’ : dp[i][j] = dp[i-1][j-1];
-
If p.charAt(j) == ‘*’:
here are two sub conditions:
-
if p.charAt(j-1) != s.charAt(i) : dp[i][j] = dp[i][j-2] //in this case, a* only counts as empty
-
if p.charAt(i-1) == s.charAt(i) or p.charAt(i-1) == ‘.’:
dp[i][j] = dp[i-1][j] //in this case, a* counts as multiple a or dp[i][j] = dp[i][j-1] // in this case, a* counts as single a or dp[i][j] = dp[i][j-2] // in this case, a* counts as empty
-
const isMatch = function (s, p) {
const m = s.length, n = p.length;
// if (m === 0 || n === 0) {
// return false;
// }
let dp = new Array();
for (let i = 0; i <= m; i++) {
dp[i] = new Array();
for (let j = 0; j <= n; j++) {
dp[i][j] = false;
}
}
dp[0][0] = true;
for (let i = 0; i < n; i++) {
if (p[i] === '*' && dp[0][i - 1]) {
dp[0][i + 1] = true;
}
}
for (let i = 0; i < m; i++) {
for (let j = 0; j < n; j++) {
if (p[j] === '.' || p[j] === s[i]) {
dp[i + 1][j + 1] = dp[i][j];
}
if (p[j] === '*') {
if (p[j - 1] !== s[i] && p[j - 1] !== '.') {
dp[i + 1][j + 1] = dp[i + 1][j - 1];
} else {
// 依次为 'a*' === '' 'a*' === 'a' 'a*' === 'n * a'
// 其实在当前条件分支中已经判定了 'a*' === 'a' 的情况了 ,所以下面的第二个判断可以删掉
dp[i + 1][j + 1] = dp[i + 1][j - 1] || dp[i + 1][j] || dp[i][j + 1];
}
}
}
}
return dp[m][n];
};