LeetCode 10 正则表达式匹配 - DP经典hard

LeetCode 10 正则匹配，Hard DP，处理好*的"匹配零次还是多次"是关键。

🔴 正则表达式匹配

实现.和*的正则匹配。.匹配任意单字符，*匹配前一个字符 0 次或多次。

如果用回溯暴力枚举*是 0 次还是 1 次还是 2 次…… 分支爆炸。DP 的角度：dp[i][j]表示 s 的前 i 个字符和 p 的前 j 个字符是否匹配。

遇到*时有两条路——匹配 0 次（把字符*当空气，跳过）、匹配 1 次（消耗 s 当前字符，*留着还能继续用）。

publicbooleanisMatch(Strings,Stringp){intm=s.length(),n=p.length();boolean[][]dp=newboolean[m+1][n+1];dp[0][0]=true;// 处理空 s 的情况：p 中 "a*" 可以匹配空for(intj=1;j<=n;j++){if(p.charAt(j-1)=='*')dp[0][j]=dp[0][j-2];}for(inti=1;i<=m;i++){for(intj=1;j<=n;j++){charsc=s.charAt(i-1),pc=p.charAt(j-1);if(pc!='*'){dp[i][j]=dp[i-1][j-1]&&(sc==pc||pc=='.');// 直接匹配}else{charprev=p.charAt(j-2);// * 前面的字符dp[i][j]=dp[i][j-2]||// * 匹配 0 次(dp[i-1][j]&&(sc==prev||prev=='.'));// * 匹配 1 次}}}returndp[m][n];}

dp[i][j - 2]是"匹配 0 次"——把字符*整个扔了。dp[i - 1][j]是"匹配 1 次"——消耗 s 的一个字符，*还留在原地（因为 j 没变，下次还能继续用）。DP 表维度是 (m+1)×(n+1)，dp[0][0] 表示两个空串匹配，记得初始化空 s 时*能消掉前一个字符的情况。

这道题你踩过什么坑？或者你用别的语言实现过吗？评论区聊聊，回头复习也方便翻。