背景

这是力扣的第10题，难度为hard

以下是题目内容的描述：

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

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

示例 1：

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

输入：s = "aa" p = "a*"
输出：true
解释：因为 '*' 代表可以匹配零个或多个前面的那一个元素, 在这里前面的元素就是 'a'。因此，字符串 "aa" 可被视为 'a' 重复了一次。
示例 3：

输入：s = "ab" p = ".*"
输出：true
解释：".*" 表示可匹配零个或多个（'*'）任意字符（'.'）。
示例 4：

输入：s = "aab" p = "c*a*b"
输出：true
解释：因为 '*' 表示零个或多个，这里 'c' 为 0 个, 'a' 被重复一次。因此可以匹配字符串 "aab"。
示例 5：

输入：s = "mississippi" p = "mis*is*p*."
输出：false

坏思路

我完全没有发现正则匹配的暴力性，一开始想到的就是简单的从头开始匹配，分别为目标字符串和表达式设置位置指针，根据“*”、“.”等匹配要素调整指针的位置，最终同时到达末尾就算成功
在遇到测试数据时我傻了，因为有一组数据是匹配类似于s="ab" p="a*b*a*b*abc*d*.*"这样子的东西，很明显，无论是从头开始匹配，还是从末尾开始匹配，都完全无法使这玩意儿匹配上，因为从两端开始是完全没办法知道当前的*是否要匹配多个字符的，而错误的匹配将会直接造成中间的ab错位，而导致最终的结果出现偏差
那，从中间开始匹配？别想了，再想就是一塌糊涂

好思路

正如上面所说，正则具有暴力性，它仿佛就像一棵树，以不同的走法搜索这棵树会带来不同的可能（所以这像一个dfs？）

递归

而说到搜索，第一个想到的就是递归。那么，对于这种正则匹配来说，递归该如何进行呢？
递归在做的事情，莫过于将大问题化为重复的小问题，而大问题则需要由小问题推导而来

对于正则来说，目标是整个字符串的匹配结果，源头则是单个字符的匹配结果，而递归的中间过程则可以为整个字符串匹配结果=(部分字符串匹配结果)&(部分字符串匹配结果)=>单个&单个&单个....匹配结果，而这些 单个字符 和 表达式 的对应关系的确立，则需要来自于上述搜索过程的摸索，毕竟在到达结果之前永远也不知道这一步走的对不对

整体思路大概就是上面所说的那样，但是到了实际操作的时候，会发现，把整个字符串，拆分成 两个 大的 部分字符串并不方便 （难道每次对半分？还是怎么分？那表达式又怎么分？）

由于拆分时需要牵扯到同时处理表达式和目标字符串的截断问题，因此唯有从前或从后开始拆分递归是可行的（否则就没法把目标字符串对应到表达式了）

以从头开始拆分来说
思路大概是这样

头部包含*时的或，巧妙的解决了上面纠结的究竟要不要去匹配，要匹配几次问题，将这个难以通过思考直接解决的问题，交给了暴力的递归尝试。

附上核心代码

bool isMatch(const char* s, const char* p) {
        if(*p == 0) return *s == 0;
        
        bool first_match = *s && (*s == *p || *p == '.');
        
        if(*(p+1) == '*'){
            return isMatch(s, p+2) || (first_match && isMatch(++s, p));
        }
        else{
            return first_match && isMatch(++s, ++p);
        }
    }

进行备忘录优化后的完整代码

class Solution {
private:
    const char *s, *p;
    int sz_s, sz_p;
    int *result;
public:
    bool isMatch(string s, string p) {
        this->s = s.c_str();
        this->p = p.c_str();
        sz_s = s.length();
        sz_p = p.length();
        result = (int *)malloc((sz_s+1) * (sz_p+1) * sizeof(int));
        memset(result, 0, sz_s * sz_p * sizeof(int));
        return isMatch(this->s, this->p);
    }
    
    bool isMatch(const char* s, const char* p) {
        int s_index = s - this->s;
        int p_index = p - this->p;

        if(*p == 0) return *s == 0;

        if (result[s_index * sz_p +p_index]==1)
            return true;
        else if(result[s_index * sz_p +p_index]==-1)
            return false;

        auto first_match = *s && (*s == *p || *p == '.');
        
        if(*(p+1) == '*'){
            if(isMatch(s, p+2) || (first_match && isMatch(++s, p))){
                result[s_index * sz_p +p_index] = 1;
                return true;
            }
            result[s_index * sz_p +p_index] = -1;
            return false;
        }
        else{
            if(first_match && isMatch(++s, ++p)){
                result[s_index * sz_p +p_index] = 1;
                return true;
            }
            result[s_index * sz_p +p_index] = -1;
            return false;
        }
    }
};

动态规划

思路和递归差不多，只不过递归是全自动从目标推到单元素，而dp则是手动从单元素推到目标

大致框架如下

总的来说，dp并不太适合人类阅读和理解

但是，就拿匹配的过程来说，dp和递归有着高度的相似性
上方的递归，使用的是从头部截取单字符匹配，而如果使用尾部截取法，那匹配的过程更是和dp完全一致

这个过程都是：从尾部截取字符，根据字符状态与前部字符串的状态，来判断当前整体的状态
只不过，dp的前部状态是需要已经算好存在数组中，而递归的前部状态则可以实现自动计算

这就使得dp对于数组的计算顺序产生了严苛的要求，计算数组中每一项的需求，都必须已经计算过

附上代码

class Solution {
public:
    bool isMatch(string s, string p) {
        int m = s.size(), n = p.size();
        vector<vector<bool>> dp(m + 1, vector<bool>(n + 1, false));
        dp[0][0] = true;
        for (int i = 0; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                if (p[j - 1] == '*') {
                    dp[i][j] = dp[i][j - 2] || (i && dp[i - 1][j] && (s[i - 1] == p[j - 2] || p[j - 2] == '.'));
                } else {
                    dp[i][j] = i && dp[i - 1][j - 1] && (s[i - 1] == p[j - 1] || p[j - 1] == '.');
                }
            }
        }
        return dp[m][n];
    }
};

i在循环的外层确保了dp[i - 1][j]的值已经提前计算好了
内层循环j从1开始，因为j=0时只有i=0才为true，而这种情况已经被处理掉了

不管怎么样，dp真是太难想了