递归改动态规划：正则匹配

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

递归解法，​原因都在注释里： ​

public class Solution {
   
   public boolean match(char[] str, char[] pattern) {
   
        return  process(str, pattern, 0, 0);
    }
 
    // 看 str[si...ends] 的字符， 能不能被 pattern[pi...ends] 所匹配
    private boolean process(char[] str, char[] pattern, int si, int pi) {
   
        // 如果 pattern 的字符走完了
        if (pi == pattern.length ) {
   
            // 看 str 字符有没有走完。 没走完就直接返回 false， 走完就是全部匹配完了。。。
            // 注意这里是 可以直接返回结果的~
            return si == str.length;
        }
        
        
        // 如果 pi 来到了最后一个字符； 或者 pi 的下一个字符 不是 *
        if (pi + 1 == pattern.length || pattern[pi + 1] != '*') {
   
            // 看 str 的情况： 
            // str要有字符可以匹配； 
            // pattern 上是 . 或者 pattern和str的字符可以匹配;
            // 都接下去一位，接着看能不能匹配。
            return si != str.length && (str[si] == pattern[pi] || pattern[pi] == '.') 
                && process(str, pattern, si+1, pi+1);
        }
        
        
        // pi 的下一个字符是 * 的情况： 
        // str 要有字符可以匹配，
        // pattern 上是 . 或者 pattern和str的字符可以匹配;
        // * 可以匹配0位或任意位：所以这个while循环就是匹配 0 ... str.length 位的情况，有true直接 返回即可
        while (si != str.length && (str[si] == pattern[pi] || pattern[pi] == '.')) {
   
            if ( process(str, pattern, si, pi+2) ) {
   
                return true;
            }
            si++;
        }
        
        // str 字符走完了， 看 pattern 之后的能不能匹配
        return process(str, pattern, si, pi+2);
    }
}

动态规划解法 ：

class Solution {
   
    public boolean isMatch(char[] str, char[] pattern) {
   
        if (str == null && pattern == null) {
   
            return true;
        }
        if (str == null || pattern == null) {
   
            return false;
        }
        int slen = str.length;
        int plen = pattern.length;
        
        // 初始化 dp 矩阵
        boolean[][] dp = initDP(str, pattern);

        // 填充 dp 矩阵
        for (int i =  slen - 1; i >= 0; i--) {
   
            for (int j = plen - 2; j >= 0; j--) {
   
                // pattern 下一位的字符不为 '*' 的情况
                if (pattern[j+1] != '*') {
   
                    // 看当前字符是否匹配， 都走一位后是否匹配
                    dp[i][j] = (str[i] == pattern[j] || pattern[j] == '.') 
                        && dp[i+1][j+1];
                } else {
   
                    // pattern 下一位的字符为 '*' 的情况
                    // * 可以匹配0位或任意位， 依次看匹配 0位、1位 ... 到末尾位的情况
                    int si = i;
                    while (si != slen && (str[si] == pattern[j] || pattern[j] == '.')) {
   
                        if (dp[si][j+2]) {
   
                            dp[i][j] = true;
                            break;
                        }
                        si++;
                    }
                    // str 走完单独算一下， 上面的 str[si] 中会越界
                    if (dp[i][j] == false) {
   
                        dp[i][j] = dp[si][j+2];
                    }
                }
            }
        }

        // 想要的结果
        return dp[0][0];
    }


    // 该 dp 矩阵中， (i, j) 依赖 (i+1, j+1) 和 (i, j+2),(i+1, j+2)...(str.length, j+2) 的位置
    // 所以， 要先把最后 2 列， 最后 1 行， 填充完整。 这样就可以推导出任何一点位置上的值了
    private boolean[][] initDP(char[] str, char[] pattern){
   
        int slen = str.length;
        int plen = pattern.length;
        boolean[][] dp = new boolean[slen+1][plen+1];
        
        // 倒数第一列, 都走完肯定为 true
        dp[slen][plen] = true;  

        // 倒数第二列, 看 pattern 和 str 的最后一个字符相不相等，或者 pattern 上是否为 '.' ; 注意边界问题
        if (slen > 0 && plen > 0 && ( str[slen-1] == pattern[plen-1] || pattern[plen-1] == '.' )) {
   
            dp[slen-1][plen-1] = true;
        }

        // 倒数第一行： str 走完了， 就看 pattern 是否可以匹配。
        for (int j = plen - 2; j >= 0; j = j - 2) {
   
            // pattern 上的字符不是 '*'， 并且下一位是 '*' ， 才能够匹配得上 ; 
            if (pattern[j] != '*' && pattern[j+1] == '*') {
   
                dp[slen][j] = true;
            } else {
   
                // 只要有 1 处开始匹配不上， 前面的就都不行， 因为pattern后面还有字符无处匹配了。
                break;  
            }
        }

        return dp;
    }
}