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

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

示例 1

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

示例 2

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

示例 3

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

示例 4

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

示例 5

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

提示

0≤∣s∣≤200\le |s|\le 20
0≤∣p∣≤300\le |p|\le 30
ss 可能为空，且只包含小写字母。
pp 可能为空，且只包含小写字母，以及字符 '.' 和 '*'。
保证每次出现字符 * 时，前面都匹配到有效的字符。

思路

默认字符串下标都从 11 开始，从 00 开始的都是sb。定义 f(i,j)f(i,j) 为 s1s2⋯sis_{1}s_2\cdots s_i 与 p1p2⋯pjp_1p_2\cdots p_j 匹配的真值。

下标从 11 开始便于考虑边界条件，两个空字符串匹配，f(0,0)=truef(0,0)=true；空字符串与形如a*b*c*...的字符串也可匹配，即 f(0,j)=j≥2∧pj=f(0,j)=j\ge 2\wedge p_j= * ∧f(0,j−2)\wedge f(0,j-2)。

最优子结构：ss 与 pp 匹配，则 ss 与 pp 必能分别分成 kk 段子串，使得 kk 段子串分别匹配。

无后效性：若 sis_i 与 pjp_j 的匹配方式确定，则此后的匹配只与当前的状态有关。

sis_i 必为小写字母，我们需要考虑 pjp_j 的字符类型。

  • pjp_j 为小写字母，必须要让 si=pjs_i=p_j 且 s1s2⋯si−1s_1s_2\cdots s_{i-1} 与 p1p2⋯pj−1p_1p_2\cdots p_{j-1} 匹配，才能使得 s1s2⋯sis_1s_2\cdots s_{i} 与 p1p2⋯pjp_1p_2\cdots p_j 匹配，f(i,j)=f(i−1,j−1)∧(si=pj)f(i,j)=f(i-1,j-1)\wedge (s_i=p_j)。

  • pjp_j 为 .，可以匹配任意字符，只需要 s1s2⋯si−1s_1s_2\cdots s_{i-1} 与 p1p2⋯pj−1p_1p_2\cdots p_{j-1} 匹配，就能使得 s1s2⋯sis_1s_2\cdots s_i 与 p0p1⋯pjp_0p_1\cdots p_j 匹配，f(i,j)=f(i−1,j−1)f(i,j)=f(i-1,j-1)。

  • pjp_j 为 *，有如下两种选择：

    • 扩展 pj−1p_{j-1}，即形成 pj−1pj−1⋯pj−1p_{j-1}p_{j-1}\cdots p_{j-1}，pj−1p_{j-1} 的个数不少于 11；
    • 不扩展 pj−1p_{j-1}，即 pj−1p_{j-1} 不出现；
    • 当 si≠pj−1s_i\neq p_{j-1} 且 pj−1≠p_{j-1}\neq .，只有 pj−1p_{j-1} 不出现才有可能使得 s1s2⋯sis_1s_2\cdots s_i 与 p1p2⋯pjp_1p_2\cdots p_j 匹配上，即 f(i,j)=f(i,j−2)f(i,j)=f(i,j-2)；
    • 当 si=pj−1s_i=p_{j-1} 或 pj−1=p_{j-1}= .，可以兼顾上述两种选择；当选择不扩展 pj−1p_{j-1}，f(i,j)=f(i,j−1)f(i,j)=f(i,j-1)；当选择扩展 pj−1p_{j-1}，f(i,j)=f(i−1,j−2)f(i,j)=f(i-1,j-2)；实际上，选择扩展时，匹配的是形如 a* 即 aaaaaaa... 这样的字符串，若 si=si−1=⋯si−ks_i=s_{i-1}=\cdots s_{i-k}，f(i,j)=⋁x=1k+1f(i−x,j−2)f(i,j)=\bigvee\limits_{x=1}^{k+1}f(i-x,j-2)，本质上是匹配了 sis_i，然后将 sis_i 扔掉，用 pj−1pjp_{j-1}p_j 继续匹配 si−1s_{i-1}，故 f(i,j)=f(i−1,j)f(i,j)=f(i-1,j)。

    代码

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    class Solution {
        public:
        bool isMatch(string s, string p) {
            const int m = s.length(), n = p.length();
            s = '\0' + s;
            p = '\0' + p;
            bool** f = new bool* [m + 1];
            for (int i = 0; i <= m; i++) {
                f[i] = new bool[n + 1];
                memset(f[i], false, sizeof(bool) * (n + 1));
            }
            f[0][0] = true;
            for (int j = 1; j <= n; j++) {
                if (j >= 2 && p[j] == '*') {
                    f[0][j] = f[0][j - 2];
                }
            }
            for (int i = 1; i <= m; i++) {
                for (int j = 1; j <= n; j++) {
                    if (isalpha(p[j])) {
                        f[i][j] = (s[i] == p[j]) & f[i - 1][j - 1];
                    } else if (p[j] == '.') {
                        f[i][j] = f[i - 1][j - 1];
                    } else {
                        if (s[i] == p[j - 1] || p[j - 1] == '.') {
                            f[i][j] = f[i - 1][j];
                            if (j >= 2) {
                                f[i][j] |= f[i][j - 2];
                            }
                        } else if (j >= 2) {
                            f[i][j] = f[i][j - 2];
                        }
                    }
                }
            }
            bool ans = f[m][n];
            for (int i = 0; i <= m; i++) {
                delete[]f[i];
            }
            return ans;
        }
    };