10.正则表达式匹配

https://leetcode-cn.com/problems/regular-expression-matching/

• • 字符必须和前面的字符搭配使用，（出现在最前面是违法的） 两个*字符连在一起是违法的
• 给你两个样本了，怎么猜呀？一个样本作行一个样本作列对应模型
• boolean f(str, exp, si, ei)
  • exp[ei……] 能不能变成 str[si…….]
  • 有个限制，f（si, ei）ei 位置不能压中， 因为以开头的不合法 (做有效性检查)
• 可能性整理
  • ei + 1 位置非*
    • str[si] == exp[ ei ] || exp[ ei ] ==”.”
      • f(si + 1, ei + 1)
      • 
  • ei + 1位置是 （因为做了有效性检查，所以ei + 2位置不可能是）
    • 如果si位置字符不等于ei位置字符（k）， 那*就让下面的那个变成0个k，然后继续下个流程
      • 
    • 若si位置字符与ei位置字符相等
      • 下边的可以变成1个a， 2个a， 3个a ， 4个a， 5个a，所有分支都去试，有一条分支能试出来，结果就是true
        • 
      • 不要错过变成0个a的时候，比如
        • 所以不管si和ei位置相不相等，0个是必试的
        • 

public class _10_正则表达式匹配 {
    public static boolean isValid(char[] s, char[] e) {
        for (int i = 0; i < s.length; i++) {
            if (s[i] == '*' || s[i] == '.') {
                return false;
            }
        }
        // 开头的e[0]不能是'*'，没有相邻的'*'
        for (int i = 0; i < e.length; i++) {
            if (e[i] == '*' && (i == 0 || e[i - 1] == '*')) {
                return false;
            }
        }
        return true;
    }
    public boolean isMatch(String str, String exp) {
        if (str == null || exp == null) return false;
        char[] s = str.toCharArray();
        char[] e = exp.toCharArray();
        return isValid(s, e) && process(s, e, 0, 0);
    }
    // e[ei....]  能否变成  s[si...]
    // 重要限制：e[ei]不能压中'*'
    private boolean process(char[] s, char[] e, int si, int ei) {
        if (ei == e.length) { // base case   exp已经耗尽了  ""
            return si == s.length;
        }
        // 可能性一，ei+1位置，不是*
        if (ei + 1 == e.length || e[ei + 1] != '*') {
            return si != s.length
                    && (e[ei] == s[si] || e[ei] == '.')
                    && process(s, e, si + 1, ei + 1);
        }
        // 可能性二，ei + 1 位置是*
        while (si != s.length && (s[si] == e[ei] || e[ei] == '.')) {
            if (process(s, e, si, ei + 2)) {
                return true;
            }
            si++;
        }
        return process(s, e, si, ei + 2);
    }
}