前言

`
给你一个字符串 s 和一个字符规律 p，请你来实现一个支持 '.' 和 '*' 的正则表达式匹配。

'.' 匹配任意单个字符
'*' 匹配零个或多个前面的那一个元素
所谓匹配，是要涵盖 整个 字符串 s的，而不是部分字符串。

示例 1：

输入：s = "aa", p = "a"
输出：false
解释："a" 无法匹配 "aa" 整个字符串。

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/regular-expression-matching
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

解题思路

样本对应模型
定义二维表
字符串有效性检查
str不能有.和*
exp开头不能是.两个不能挨着

    public static boolean isValid(char[] s, char[] e) {
        // s中不能有'.' or '*'
        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;
    }

暴力递归

递归含义:
str从si出发及其后面的所有,能不能被exp从ei出发及其后面的所有配出来
能配出来返回true,否则false
1) ei下一个位置不是*
如果ei+1不是 ，就说明我e没有操作空间了。它不能指望后面的 把它变没,代表此时si必须能和ei对上
只能是[ei]字符等于[si]字符
要么[ei]字符是 . ,它能够变成一切

2) ei+1是*
0)变零个

让a*变0个a,后面去匹配
1)变1个a
2)变2个a
3) 3个a
4) 4个a

每一种分支全都走，但有一个走通，直接返回true,所有分支都走不通，返回false,

    public static boolean isMatch1(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);
    }

    // str[si.....] 能不能被 exp[ei.....]配出来！ true false
    public static boolean process(char[] s, char[] e, int si, int ei) {
        if (ei == e.length) { // exp 没了 str？
            return si == s.length;
        }
        // exp[ei]还有字符
        // ei + 1位置的字符，不是*
        if (ei + 1 == e.length || e[ei + 1] != '*') {
            // ei + 1 不是*
            // str[si] 必须和 exp[ei] 能配上！
            return si != s.length && (e[ei] == s[si] || e[ei] == '.') && process(s, e, si + 1, ei + 1);
        }
        // exp[ei]还有字符
        // ei + 1位置的字符，是*!
        while (si != s.length && (e[ei] == s[si] || e[ei] == '.')) {
            if (process(s, e, si, ei + 2)) {
                return true;
            }
            si++;
        }
        return process(s, e, si, ei + 2);
    }

斜率优化+记忆化搜索

f(13, 29)的依赖

f(12, 29)的依赖
f(12, 29)=f(13,29)+f(12,31)
在str中i位置字符和str中i+ 1位置字符它一样的时候就存在这个优化

当我一-个格子有枚举行为的时候，我就观察他已经算过的格子,能不能把枚举行为替代掉,
从而得到一一个使用有限若干个位置的方式来得到这一个格子的值

    public static boolean isMatch2(String str, String exp) {
        if (str == null || exp == null) {
            return false;
        }
        char[] s = str.toCharArray();
        char[] e = exp.toCharArray();
        if (!isValid(s, e)) {
            return false;
        }
        int[][] dp = new int[s.length + 1][e.length + 1];
        // dp[i][j] = 0, 没算过！
        // dp[i][j] = -1 算过，返回值是false
        // dp[i][j] = 1 算过，返回值是true
        return isValid(s, e) && process2(s, e, 0, 0, dp);
    }

    public static boolean process2(char[] s, char[] e, int si, int ei, int[][] dp) {
        if (dp[si][ei] != 0) {
            return dp[si][ei] == 1;
        }
        boolean ans = false;
        if (ei == e.length) {
            ans = si == s.length;
        } else {
            if (ei + 1 == e.length || e[ei + 1] != '*') {
                ans = si != s.length && (e[ei] == s[si] || e[ei] == '.') && process2(s, e, si + 1, ei + 1, dp);
            } else {
                if (si == s.length) { // ei ei+1 *
                    ans = process2(s, e, si, ei + 2, dp);
                } else { // si没结束
                    if (s[si] != e[ei] && e[ei] != '.') {
                        ans = process2(s, e, si, ei + 2, dp);
                    } else { // s[si] 可以和 e[ei]配上
                        ans = process2(s, e, si, ei + 2, dp) || process2(s, e, si + 1, ei, dp);
                    }
                }
            }
        }
        dp[si][ei] = ans ? 1 : -1;
        return ans;
    }