$$\color{Red}{【困难】正则匹配字符串【leetcode10 正则DP】}$$

下面的链接是——————我做的所有的题解

包括基础提高以及一些零散刷的各种各样的题

给你一个字符串 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
解释：".*" 表示可匹配零个或多个（'*'）任意字符（'.'）。

提示：

• 1 <= s.length <= 20
• 1 <= p.length <= 20
• s 只包含从 a-z 的小写字母。
• p 只包含从 a-z 的小写字母，以及字符 . 和 *。
• 保证每次出现字符 * 时，前面都匹配到有效的字符

解析

从集合的角度来思考问题，用一个可以递推的公式，表示一种状态，能从一种状态不断迭代，表示更新的状态。

我们这里考虑 f[i][j] 表示从模板串 s 的前 i 个字符，和正则串 p 的前 j 个字符进行匹配，表示状态为能否转移而来。

那么我们需要考虑集合划分的方式，我们可以考虑 s[j] 是否为 * 作为划分的条件。

为什么？

首先， s[i] 只能等于相同字符，或者 * 或 .，而 . 可以看作任意的一个字符，我们可以把 . 的情况纳入字符匹配的或逻辑运算符号，而如果是 * 的情况，就不能单独用正则串的这一位和模板串比较，还需要考虑 * 前面第一个不为 * 的符号加以判断，或者是排除这两个符号来匹配。

【s[i] == p[j - 2] 即p[j-1]出现 0 次】，同时当p[j] != * 判断 f[i][j] 合法的前提，还需要判断 f[i-1][j-1] 也需要满足匹配。

p[j] == * 该如何考虑？

首先是上面提到的情况下是合法的：排除这两个符号来匹配 ：【s[i] == p[j - 2] 即p[j-1]出现 0 次】

其次我们要考虑，到底 s 串哪些字符被 p 串的正则符号匹配，而匹配之前的符号，要满足也和正则串符号之前的也匹配。

这里定义符号 T[i] 表示 正则串 p[j-1] 的符号 和 模板串的 s[i] 符号达成匹配，即满足

(p.charAt(i) == s.charAt(j-1)) || s.charAt(j-1) == '.'

分别考虑 x* 能匹配模板串的字符个数，一旦存在一个满足匹配的情况，则此时说明正则匹配合法。

            匹配 0 个          匹配 1 个                      匹配 2 个
f[i][j] = (f[i][j-2]) || (f[i-1][j-2] & T[i]) || (f[i-2][j-2] && T[i] && T[i-1]) || ......

那此时需要 O(n ^ 3) 时间复杂度，如何优化？

考虑到此时类似完全背包模型，可以考虑到能容纳的极限个即满足 全部字符均匹配的情况。

那么我们考虑上一层状态是否可以联系本层。

            匹配 0 个          匹配 1 个                      匹配 2 个
f[i-1][j] = (f[i-1][j-2]) || (f[i-2][j-2] & T[i-1]) || (f[i-3][j-2] && T[i-1] && T[i-2]) || ...

与下面的当前层对比可发现，相当于除第一项外，每一项少了一个与 T[i] 相与运算，即可以直接优化到第二维度             

f[i][j] = (f[i][j-2]) || (f[i-1][j-2] & T[i]) || (f[i-2][j-2] && T[i] && T[i-1]) || ......   

与下面的当前层对比可发现，相当于除第一项外，每一项少了一个与 T[i] 相与运算，即可以直接优化到第二维度

i从0开始就是针对s=”aa”,p=”a*”这样的条件，靠i=0时把f[0][2]设为true，使其符合题意。

class Solution {
    public boolean isMatch(String s, String p) {
        int n = s.length(),m = p.length();
        s = " " + s;
        p = " " + p;

        boolean[][] f = new boolean[n + 3][m + 3];

        f[0][0] = true;

        for (int i = 0; i <= n; i ++)
            for (int j = 1; j <= m; j ++) {
                if (p.charAt(j) != '*') {
                    boolean flag = (s.charAt(i) == p.charAt(j) || p.charAt(j) == '.');
                    f[i][j] = i != 0 && f[i-1][j-1] && flag;
                } else {
                    boolean flag = (s.charAt(i) == p.charAt(j-1) || p.charAt(j-1) == '.');
                    f[i][j] = f[i][j-2] || (i != 0 && f[i-1][j] && flag);
                }
            }

        return f[n][m];
    }
}