https://leetcode-cn.com/problems/wildcard-matching/

• 这题跟第10题有点像，但又不完全一样

  一个样本做行一个样本做列对应模型

  递归

  枚举行为
  

    //递归
    public boolean isMatch(String str, String pattern) {
        char[] s = str.toCharArray();
        char[] p = pattern.toCharArray();
        return process(s, p, 0, 0);
    }
    //s[si....] 能否与 p[pi.....] 匹配
    private boolean process(char[] s, char[] p, int si, int pi) {
        if (si == s.length) { // si到终点了
            if (pi == p.length) { //pi也到终点
                return true;
            } else { 
                return p[pi] == '*' && process(s, p, si, pi + 1);
            }
        }
        // si != s.length
        if (pi == p.length) {
            return false;
        }
        if (p[pi] != '?' && p[pi] != '*') {
            return s[si] == p[pi] && process(s, p, si + 1, pi + 1);
        }
        if (p[pi] == '?') {
            return process(s, p, si + 1, pi + 1);
        }
        // p[pi] == '*' 
        // 枚举行为: * 匹配 s[si...si]
        //          * 匹配 s[si...si + 1]
        //          * 匹配 s[si...si + 2]
        //           .........
        for (int len = 0; len <= s.length - si; len++) {
            if (process(s, p, si + len, pi + 1)) {
                return true;
            }
        }
        return false;
    }

递归改动态规划

public boolean isMatch2(String str, String pattern) {
    char[] s = str.toCharArray();
    char[] p = pattern.toCharArray();
    int N = s.length;
    int M = p.length;
    boolean[][] dp = new boolean[N + 1][M + 1];
    dp[N][M] = true;
    for (int pi = M - 1; pi >= 0; pi--) {
        dp[N][pi] = p[pi] == '*' && dp[N][pi + 1];
    }
    for (int si = N - 1; si >= 0; si--) {
        for (int pi = M - 1; pi >= 0; pi--) {
            if (p[pi] != '?' && p[pi] != '*') {
                dp[si][pi] = s[si] == p[pi] && dp[si + 1][pi + 1];
                continue;
            }
            if (p[pi] == '?') {
                dp[si][pi] = dp[si + 1][pi + 1];
                continue;
            }
            // p[pi] == '*'
            for (int len = 0; len <= s.length - si; len++) {
                if (dp[si + len][pi + 1]) {
                    dp[si][pi] = true;
                    break;
                }
            }
        }
    }
    return dp[0][0];
}

斜率优化

有枚举行为（pi位置字符是* 的时候）

观察临近的格子看能不能把枚举行为省掉

（4，8）位置的值与（5，7）位置的值或，就可以了

 public boolean isMatch3(String str, String pattern) {
     char[] s = str.toCharArray();
     char[] p = pattern.toCharArray();
     int N = s.length;
     int M = p.length;
     boolean[][] dp = new boolean[N + 1][M + 1];
     dp[N][M] = true;
     for (int pi = M - 1; pi >= 0; pi--) {
         dp[N][pi] = p[pi] == '*' && dp[N][pi + 1];
     }
     for (int si = N - 1; si >= 0; si--) {
         for (int pi = M - 1; pi >= 0; pi--) {
             if (p[pi] != '?' && p[pi] != '*') {
                 dp[si][pi] = s[si] == p[pi] && dp[si + 1][pi + 1];
                 continue;
             }
             if (p[pi] == '?') {
                 dp[si][pi] = dp[si + 1][pi + 1];
                 continue;
             }
             // p[pi] == '*'
             dp[si][pi] = dp[si][pi + 1] || dp[si + 1][pi];
         }
     }
     return dp[0][0];
 }