剑指offer 19.正则表达式匹配（动态规划）

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

示例 1:
输入:
s = "aa"
p = "a"
输出: false
解释: "a" 无法匹配 "aa" 整个字符串。

示例 2:
输入:
s = "aa"
p = "a"
输出: true
解释: 因为 '' 代表可以匹配零个或多个前面的那一个元素, 在这里前面的元素就是 'a'。因此，字符串 "aa" 可被视为 'a' 重复了一次。

示例 3:
输入:
s = "ab"
p = "."
输出: true
解释: "." 表示可匹配零个或多个（'*'）任意字符（'.'）。

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

示例 5:
输入:
s = "mississippi"
p = "misisp*."
输出: false
s 可能为空，且只包含从 a-z 的小写字母。
p 可能为空，且只包含从 a-z 的小写字母以及字符 . 和 ，无连续的 ''。

solution：动态规划
定义：数组 dp[i][j] 标志字符串 s 的前 i 个与字符串 p 的前 j 个是否匹配。
状态转移：
1.空正则且空字符串，可匹配；
2.非空正则，分为最后一个字符是 '*' 和非 '*' 两种情况:
①非 '*'：若 s 不为空且 s[i] == p[j]，则 dp[i][j] == dp[i-1][j-1]；
②'*'：遇到这种情况，若模式串长度大于2，直接看 c* 之前的正则串是否匹配，若匹配，则 c*可以匹配空字符，即 dp[i][j] |= dp[i][j-2]；
然后再考虑 c*，若 (A[i]==B[j-1]||B[j-1]==".") 为真，则A往前看一位，B的c*仍可匹配字符A[i]，即 dp[i][j] |= dp[i-1][j]；
①②两种情况非互斥，因此结果做或运算。

class Solution {
    public boolean isMatch(String s, String p) {
        int n = s.length();
        int m = p.length();
        boolean[][] dp = new boolean[n+1][m+1];

        for(int i=0; i<=n; i++){
            for(int j=0; j<=m; j++){
                //空正则、非空正则
                if(j == 0){
                    //空正则，若s也为空，可匹配
                    dp[i][j] = (i == 0); 
                }
                else{
                    //非空正则分为两种情况 * 和 非*
                    if(p.charAt(j-1) != '*'){
                        if(i>0 && (s.charAt(i-1)==p.charAt(j-1) || p.charAt(j-1)=='.')){
                            dp[i][j] = dp[i-1][j-1];
                        }
                    }
                    else{
                        //碰到*，分为看和不看两种情况，依次讨论
                        //不看，若模式串长度大于2，直接看c*之前的正则串是否匹配
                        if(j>=2){
                            dp[i][j] |= dp[i][j-2];
                        }
                        //看，若(A[i]==B[j-1]||B[j-1]==".")为真，则A往前移一位，B的c*仍可匹配字符c，因此不动
                        if(i>=1 && j>=2 && (s.charAt(i-1) == p.charAt(j-2) || p.charAt(j-2) == '.')){
                            dp[i][j] |= dp[i-1][j];
                        }
                    }
                }
            }
        }
        return dp[n][m];
    }
}