通配符——*可以当0或任意个前方字符（二）

LeetCode_10_RegularExpressionMatching

题目分析：

 以 s="aaa" p = "ab*a*c*a"为例
      a b * a * c * a
    T F F F F F F F F
  a F T F T F T F T F
  a F F F F T T F T T
  a F F F F F T F T T

和上题一样 '.'和相配的情况依旧，看*的情况，只是*的使用方式多了一层分类。
1.p.charAt(j - 1) != '*'
  dp[i][j] = dp[i - 1][j - 1] && (s.charAt(i - 1) == p.charAt(j - 1) || p.charAt(j - 1) == '.');
2.p.charAt(j - 1) == '*' 分类 
  这里有个和上一题的本质区别，*的分类取决于*前面的值，所以多一层分类。
  2.1如果 p[j - 2]和s[i - 1]不能配上  s:"b" p:"a*"这种情况
  也就是 s.charAt(i - 1) != p.charAt(j - 2) && p.charAt(j - 2) != '.'
  那么只能配0个 dp[i][j] = dp[i][j - 2];
  2.2如果配得上那么  s:"a" p:"a*"这种情况
  
    2.2.1 0个   dp[i][j - 2] s="a"   p="aa*"
    2.2.2 1个   dp[i][j - 1] s="aa"  p="aa*"
    2.2.3 多个  dp[i - 1][j] s="aaa" p="aa*"

    dp[i][j] = dp[i][j - 2] || dp[i][j - 1] || dp[i - 1][j];

解法一：

public static boolean isMatch(String s, String p) {
    int m = s.length(), n = p.length();
    boolean dp[][] = new boolean[m + 1][n + 1];
    dp[0][0] = true;
    /**
     * 初始项 默认了输入数据不可能以*开头！
     *  s ""
     *  p "a*"
     *  这种情况看初始项 如果为*那么*前可以为0个 所以对应的dp[i][j - 2]位置如果可配 那么一定可配
     */
    for (int i = 1; i <= p.length(); i++) {
        if(p.charAt(i - 1) == '*')
            dp[0][i] = dp[0][i - 2];
    }
    for (int i = 1; i <= m; ++i) {
        for (int j = 1; j <= n; ++j) {
            if(p.charAt(j - 1) == '*'){
                /**
                 * 是* 那么 *当0个还是多个
                 */
                if(s.charAt(i - 1) != p.charAt(j - 2) && p.charAt(j - 2) != '.'){
                    /**
                     *  s "b"
                     *  p "a*"
                     *  上一个值不等
                     * 只能当0个
                     */
                    dp[i][j] = dp[i][j - 2];
                }else {
                    /**
                     *  上一个相等
                     * 可能当0或多个
                     *  s "a"
                     *  p "a*"
                     *  0个   dp[i][j - 2] s="a" p="aa*"
                     *  1个   dp[i][j - 1] s="aa" p="aa*"
                     *  多个  dp[i - 1][j] s="aaa" p="aa*"
                     */
                    dp[i][j] = dp[i][j - 2] || dp[i][j - 1] || dp[i - 1][j];
                }
            }else {
                dp[i][j] = dp[i - 1][j - 1] && (s.charAt(i - 1) == p.charAt(j - 1) || p.charAt(j - 1) == '.');
            }
        }
    }
    return dp[m][n];
}

解法二：

public static boolean isMatch(String s, String p) {
    /**
     * p是空 那么是有s是空能配上
     */
    if (p.isEmpty()) return s.isEmpty();
    /**
     * p(1)是* 与否 直接迭代 反正都递归了 也就将上方的循环写成了递归
     * 本质还是 等于*时 将*前一个数 从0次开始 依次使用
     */
    if (p.length() > 1 && p.charAt(1) == '*') {
        /**
         * 左方是用0次 右方是+1次
         * isMatch2(s.substring(1, s.length()), p) 这个写法 s配了一个 p不变
         * 是+1次的成型所在
         */
        return isMatch(s, p.substring(2, p.length())) || (! s.isEmpty() && (s.charAt(0) == p.charAt(0) || p.charAt(0) == '.') && isMatch(s.substring(1, s.length()), p));
    } else {
        return !s.isEmpty() && (s.charAt(0) == p.charAt(0) || p.charAt(0) == '.') && isMatch(s.substring(1, s.length()), p.substring(1, p.length()));
    }
}