LeetCode 10 正则匹配Hard DP处理好*的匹配零次还是多次是关键。 正则表达式匹配实现.和*的正则匹配。.匹配任意单字符*匹配前一个字符 0 次或多次。如果用回溯暴力枚举*是 0 次还是 1 次还是 2 次…… 分支爆炸。DP 的角度dp[i][j]表示 s 的前 i 个字符和 p 的前 j 个字符是否匹配。遇到*时有两条路——匹配 0 次把字符*当空气跳过、匹配 1 次消耗 s 当前字符*留着还能继续用。publicbooleanisMatch(Strings,Stringp){intms.length(),np.length();boolean[][]dpnewboolean[m1][n1];dp[0][0]true;// 处理空 s 的情况p 中 a* 可以匹配空for(intj1;jn;j){if(p.charAt(j-1)*)dp[0][j]dp[0][j-2];}for(inti1;im;i){for(intj1;jn;j){charscs.charAt(i-1),pcp.charAt(j-1);if(pc!*){dp[i][j]dp[i-1][j-1](scpc||pc.);// 直接匹配}else{charprevp.charAt(j-2);// * 前面的字符dp[i][j]dp[i][j-2]||// * 匹配 0 次(dp[i-1][j](scprev||prev.));// * 匹配 1 次}}}returndp[m][n];}dp[i][j - 2]是匹配 0 次——把字符*整个扔了。dp[i - 1][j]是匹配 1 次——消耗 s 的一个字符*还留在原地因为 j 没变下次还能继续用。DP 表维度是 (m1)×(n1)dp[0][0] 表示两个空串匹配记得初始化空 s 时*能消掉前一个字符的情况。这道题你踩过什么坑或者你用别的语言实现过吗评论区聊聊回头复习也方便翻。