正则表达式匹配

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

示例

输入:
s = "aab"
p = "c*a*b"
输出: true
解释: 因为 '*' 表示零个或多个，这里 'c' 为 0 个, 'a' 被重复一次。因此可以匹配字符串 "aab"。
输入:
s = "ab"
p = ".*"
输出: true
解释: ".*" 表示可匹配零个或多个（'*'）任意字符（'.'）。

注意

1、对匹配的理解：模式串p能够组合出现与待匹配的字符串一样的字符串，叫做模式串能够匹配该字符串
2、的含义：前面的字符出现0,1,2…..次。而不是*这个字符的位置出现0,1,2…..次前面的字符
3、需要注意状态中每一维下标与实际字符下标的对应关系。

解题

使用动态规划，对匹配的方案进行枚举，每轮添加一个字符并判断是否能匹配，直至添加完整个字符串
从 A[:1] 和 B[:1] 是否能匹配开始判断
dp[i][j]表示： A 的前 i 个字符与 B 中的前 j 个字符是否能够匹配。
dp[i][j] 对应： 添加字符是 s[i - 1] 和 p[j - 1]
在进行状态转移时，考虑 p 的第 j 个字符的匹配情况，正常字符、*和 .（点），针对这三种情况讨论。

1.求字符串和模式串的长度，初始化 dp 数组
2.两层for循环：
1.特值（空正则）：空串和空正则 -> 匹配
非空串和空正则 -> 不匹配
空串和非空正则/非空串和非空正则 -> 需要计算
2.计算非空正则：
<1>模式串遍历到当前为小写字母或者 ‘.’ ：
p的第j-1个字符和s的第j-1个字符相等 / p的第j-1个字符是 ‘.’ -> dp[i][j] = dp[i-1][j-1]
不相等直接不匹配
<2>模式串遍历到当前为 ‘‘ :
和前面字母出现0次【模式串后退两步】： -> dp[i][j] = dp[i][j-2]
*和前面字母出现一次或以上：【主串后退一步】
p的第j-2个字符和s的第j-1个字符相等 / p的第j-2个字符是 ‘.’ -> dp[i][j] = dp[i-1][j]
不相等直接不匹配
3.返回dp[m][n]

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];
        for(int i = 0; i<=m; i++){
            for(int j = 0; j<=n; j++){
                //分成空正则和非空正则两种
                if(j == 0){
                    dp[i][j] = (i==0);
                }
                else{
                    //非空正则分为两种情况 非*  和  *
                    if(p.charAt(j-1) != '*'){
                        if(i >0 && (p.charAt(j-1) == s.charAt(i-1) || p.charAt(j-1) == '.')){
                            dp[i][j] = dp[i-1][j-1];
                        }
                    }
                    else{
                        //碰到 * 了，分为看和不看两种情况
                        //不看
                        if(j>=2){
                            dp[i][j] |= dp[i][j-2];
                        }
                        //看
                        if(i>0 && j>1 && (p.charAt(j-2) == s.charAt(i-1) || p.charAt(j-2) =='.')){
                            dp[i][j] |= dp[i-1][j];
                        }
                    }
                }
            }
        }
        return dp[m][n];
    }
}