这题是 LeetCode 里非常经典的DP 入门天花板题。它难的点不在代码而在于*不是单独工作的它永远作用于前一个字符。比如a*→、a、aa、aaa都行.*→ 任意字符串一、核心定义定义dp[i][j]表示s前i个字符是否能被p前j个字符匹配。注意i和j表示长度所以dp[0][0] true空串匹配空串二、普通字符怎么匹配如果s[i - 1] p[j - 1]或者p[j - 1] .说明当前字符可以匹配。那么dp[i][j] dp[i - 1][j - 1]意思前面匹配成功当前字符也能对上那整体就成功。例如s ab p ab最后b b所以看前面dp[2][2] dp[1][1]三、最难的部分*这是整题核心。*有两种情况假设a*现在看*情况1匹配 0 次比如s b p a*b这里a* - 直接忽略。所以dp[i][j] dp[i][j - 2]为什么是j - 2因为a*两个字符一起删掉。情况2匹配 1 次比如s aaa p a*当前字符s[i - 1]必须能和p[j - 2]匹配。因为* 前面的字符才是真正重复的东西。匹配条件s[i - 1] p[j - 2]或者p[j - 2] .如果能匹配dp[i][j] | dp[i - 1][j]意思当前这个字符被*吃掉一个。然后继续看看前面的字符串还能不能继续被 a* 匹配四、完整转移公式普通字符 / .if (s.charAt(i - 1) p.charAt(j - 1) || p.charAt(j - 1) .) { dp[i][j] dp[i - 1][j - 1]; }*if (p.charAt(j - 1) *) {1. 匹配 0 次dp[i][j] dp[i][j - 2];2. 匹配多次如果s.charAt(i - 1) p.charAt(j - 2)或者p.charAt(j - 2) .那么dp[i][j] | dp[i - 1][j];五、初始化这是很多人最容易错的。空串 vsa*b*c*例如s p a*b*是可以匹配的。所以for (int j 2; j n; j) { if (p.charAt(j - 1) *) { dp[0][j] dp[0][j - 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]; dp[0][0] true; // 初始化空串情况 for (int j 2; j n; j) { if (p.charAt(j - 1) *) { dp[0][j] dp[0][j - 2]; } } for (int i 1; i m; i) { for (int j 1; j n; j) { // 普通字符 或 . if (s.charAt(i - 1) p.charAt(j - 1) || p.charAt(j - 1) .) { dp[i][j] dp[i - 1][j - 1]; } // * else if (p.charAt(j - 1) *) { // 匹配0次 dp[i][j] dp[i][j - 2]; // 匹配多次 if (s.charAt(i - 1) p.charAt(j - 2) || p.charAt(j - 2) .) { dp[i][j] | dp[i - 1][j]; } } } } return dp[m][n]; } }七、真正理解dp[i - 1][j]这是整题最关键的一步。很多人死活理解不了dp[i - 1][j]为什么不是dp[i - 1][j - 1]看这个s aaa p a*当处理最后一个a时前面两个 a 仍然还能继续被 a* 匹配所以模式不动 字符串减少因此dp[i - 1][j]不是dp[i - 1][j - 1]因为a* 还没用完八、这题本质是什么本质是*让状态出现“留在当前位置”的可能。普通匹配(i, j) - (i-1, j-1)而*(i, j) - (i-1, j)这就是这题从中等变困难的原因。这题如果你真正吃透了编辑距离通配符匹配字符串 DP状态机 DP都会顺很多。