摘要

剑指 Offer 19. 正则表达式匹配

请实现一个函数用来匹配包含'. '和'*'的正则表达式。模式中的字符'.'表示任意一个字符，而'*'表示它前面的字符可以出现任意次（含0次）。在本题中，匹配是指字符串的所有字符匹配整个模式。例如，字符串"aaa"与模式"a.a"和"ab*ac*a"匹配，但与"aa.a"和"ab*a"均不匹配。

一、动态规划解析

假设主串为A，模式串为B从最后一步出发，需要关注最后进来的字符。假设A的长度为n ，B的长度为m ，关注正则表达式B 的最后一个字符是谁，它有三种可能，正常字符、∗ 和 .（点），那针对这三种情况讨论即可，如下：

• 如果B的最后一个字符是正常字符，那就是看 A[n−1]是否等于 B[m−1]，相等则看A0..n−2与 B0..m−2，不等则是不能匹配，这就是子问题。
• 如果B的最后一个字符是.，它能匹配任意字符，直接看 A0..n−2与B0..m−2。
• 如果B的最后一个字符是*它代表 B[m−2]=c可以重复0次或多次，它们是一个整体 c∗
•        情况一：A[n−1]是0个c，B最后两个字符废了，能否匹配取决于 A0..n−1和 B0..m−3是否匹配。
•       情况二：A[n−1]是多个c中的最后一个（这种情况必须 A[n−1]=c或者 c=′.’），所以A匹配完往前挪一个，B继续匹配，因为可以匹配多个，继续看 A0..n−2和 B0..m−1​是否匹配。

转移方程

f[i][j]代表A 的前i个和B的前j个能否匹配

• 对于前面两个情况，可以合并成一种情况 f[i][j]=f[i−1][j−1]
• 对于第三种情况，对于c∗分为看和不看两种情况
•       不看：直接砍掉正则串的后面两个， f[i][j]=f[i][j−2]
•        看：正则串不动，主串前移一个，f[i][j]=f[i−1][j]

初始条件

特判：需要考虑空串空正则

• 空串和空正则是匹配的，f[0][0]=true
• 空串和非空正则，不能直接定义true和false，必须要计算出来。（比如A='' '' ,B=a∗b∗c∗）
•        非空串和空正则必不匹配，f[1][0]=...=f[n][0]=false
•        非空串和非空正则，那肯定是需要计算的了。

大体上可以分为空正则和非空正则两种，空正则也是比较好处理的，对非空正则我们肯定需要计算，非空正则的三种情况，前面两种可以合并到一起讨论，第三种情况是单独一种，那么也就是分为当前位置是∗和不是∗两种情况了。我们开数组要开n+1，这样对于空串的处理十分方便。结果就是 f[n][m]。

package DP;/*** @Classname JZ19正则表达式匹配* @Description TODO* @Date 2023/3/3 19:42* @Created by xjl*/
public class JZ19正则表达式匹配 {public boolean isMatch(String A, String B) {int n = A.length();int m = B.length();boolean[][] f = new boolean[n + 1][m + 1];for (int i = 0; i <= n; i++) {for (int j = 0; j <= m; j++) {//分成空正则和非空正则两种if (j == 0) {f[i][j] = i == 0;} else {//非空正则分为两种情况 * 和 非*if (B.charAt(j - 1) != '*') {if (i > 0 && (A.charAt(i - 1) == B.charAt(j - 1) || B.charAt(j - 1) == '.')) {f[i][j] = f[i - 1][j - 1];}} else {//碰到 * 了，分为看和不看两种情况//不看if (j >= 2) {f[i][j] |= f[i][j - 2];}//看if (i >= 1 && j >= 2 && (A.charAt(i - 1) == B.charAt(j - 2) || B.charAt(j - 2) == '.')) {f[i][j] |= f[i - 1][j];}}}}}return f[n][m];}
}

博文参考

《leetcode》