10. 正则表达式匹配

给你一个字符串 s 和一个字符规律 p，请你来实现一个支持 '.' 和 '*' 的正则表达式匹配。
‘.’ 匹配任意单个字符
‘*’ 匹配零个或多个前面的那一个元素

所谓匹配，是要涵盖 整个 字符串 s的，而不是部分字符串。
说明:

• s 可能为空，且只包含从 a-z 的小写字母。
• p 可能为空，且只包含从 a-z 的小写字母，以及字符 . 和 *。

  示例 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 = “cab”
输出: true
解释: 因为 ‘*’ 表示零个或多个，这里 ‘c’ 为 0 个, ‘a’ 被重复一次。因此可以匹配字符串 “aab”。

示例 5:

输入:
s = “mississippi”
p = “misisp.”
*输出: false

动态规划

从左往右扫的话
字符后面是否跟着星号会影响结果，分析起来有点复杂。

选择从右往左扫描
星号前面肯定有一个字符，星号也只影响这一个字符。

• s、p 串是否匹配，取决于：最右端是否匹配、剩余的子串是否匹配。
• 只是最右端可能是特殊符号，需要分情况讨论而已。

通用地表示出子问题**

• 大子串是否匹配，和剩余子串是否匹配，是规模不一样的同一问题

情况1：s[i-1]和 p[j-1] 是匹配的

• s、p的右端是匹配的，大问题的答案 = 剩余子串是否匹配

情况2：s[i-1]和 p[j-1]是不匹配的

• 右端不匹配，还不能判死刑——可能是 p[j-1]p[j−1] 为星号造成的不匹配，星号不是真实字符，它不匹配不算数。
• 如果 p[j-1]p[j−1] 不是星号，那就真的不匹配了。

p[j-1]==”*”，且 s[i-1] 和 p[j-2] 匹配

• p[j-1] 是星号，s[i-1] 和 p[j-2] 匹配，要考虑三种情况：
  • p[j-1] 这个星号可以让 p[j-2] 在 p 串中消失、出现 1 次、出现 >=2 次
  • 只要其中一种情况使得剩余子串能匹配，那就能匹配，见下图 a1、a2、a3

• a3 情况：假设 s 的右端是一个 a，p 的右端是 a ， 让a重复 >= 2 次
  • 星号不是真实字符，s、p是否匹配，要看 s 去掉末尾的 a，p 去掉末尾一个a，剩下的是否匹配
  • 星号拷贝出 >=2 个 a，拿掉一个，剩下 >=1 个a，p 末端依旧是 a* 没变
  • s 末尾的 a 被抵消了，继续考察 s(0,i-2) 和 p(0,i-1) 是否匹配

p[j-1]==”*”，但 s[i-1] 和 p[j-2] 不匹配

• s[i-1] 和 p[j−2] 不匹配，还有救，p[j−1] 这个星号可以让 p[j−2] 消失，继续考察 s(0,i-1) 和 p(0,j-3)

base case

• p为空串，s不为空串，肯定不匹配。
• s为空串，但p不为空串，要想匹配，只可能是右端是星号，干掉一个字符后，把 p 变为空串，才能匹配。
• s、p都为空串，肯定匹配。

代码

class Solution:
    def isMatch(self, s: str, p: str) -> bool:
        s_len, p_len = len(s), len(p)
        # dp[i][j] 表示 s[:i] 与 p[:j] 是否匹配，各自前 i、j 个是否匹配
        dp = [[False] * (p_len + 1) for _ in range(s_len + 1)]
        dp[0][0] = True
        # s 为空串
        for j in range(1, p_len + 1):
            # 若 p 的第 j 个字符 p[j - 1] 是 '*'
            # 说明第 j - 1、j 位可有可无
            # 那么如果前 j - 2 个已经匹配上，前 j 个也可以匹配上
            if p[j - 1] == '*':
                dp[0][j] = dp[0][j - 2]
        for i in range(1, s_len + 1):
            for j in range(1, p_len + 1):
                if p[j - 1] in {s[i - 1], '.'}:
                    dp[i][j] = dp[i - 1][j - 1]
                elif p[j - 1] == '*':
                    if p[j - 2] in {s[i - 1], '.'}:
                        dp[i][j] = dp[i][j - 2] or dp[i - 1][j - 2] or dp[i - 1][j]
                    else:
                        dp[i][j] = dp[i][j - 2]
        return dp[s_len][p_len]