LeetCode_10_困难_正则表达式匹配

1. 题目

给你一个字符串 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 的小写字母，以及字符 . 和 *
• 保证每次出现字符 * 时，前面都匹配到有效的字符

2. 思路及代码实现（Python）

2.1 动态规划

题目要求判断字符串 s 是否能够被 p 匹配，显然字符串每一部分都能被 p 的相应部分匹配，因此可以用动态规划减少前序部分的匹配。

我们取出字符串 s 的前 i 个字符串，并用 p 的前 j 个字符串匹配，匹配结果设为 f[i][j]，在不考虑特殊匹配符情况下，显然当 $s[i]=p[j]\Rightarrow f[i][j]=f[i-1][j-1]$，反之，则返回 False。

若考虑 . 和 *，就要额外进行判断。如果 p 中的字符为 .，则与 s 取出的任意字符都能够匹配。而 * 被认为是可以复制前一个字符的0次或多次，因此当我们取出 p 的前 j 个数时，第 j 个数为 *，则需要判断字符串 s 取出的部分是不是能匹配上。假如，* 的复制次数为0，那么 $f[i][j]|=f[i][j-2]$，说明* 及前一个字符都不生效。

从字符串 s 的角度，假设 abcdddd 中 abc 匹配 abcd* 时，此时 * 复制次数为0，该组合能够匹配成功；进一步地，abcd 和 abcd* 是在 abc[d] == abc[d]* 的前提下，基于 f[i-1][j] 进行判断的，因此最终的状态转移逻辑为：

• p 末尾是否为 *：
  • 是：
    • 若 * 复制0次时能匹配则 f[i][j]=0
    • 若 * 复制1次及以上，则判断 s 子字符串末尾字符是不是匹配 * 前的字符，若匹配，则 f[i][j] |= f[i-1][j]
  • 否：则按照两个字符串末尾值是否相匹配进行判断
    • 匹配：f[1][j] |= f[i-1][j-1]
    • 不匹配：返回 False

以上算法的时间复杂度为 O(mn)，其中 m和n分别是字符串 s和 p 的长度，空间复杂度为 O(mn)，存储着各个长度组合的匹配结果。

class Solution:
    def isMatch(self, s: str, p: str) -> bool:
        m, n = len(s), len(p)

        def matches(i: int, j: int) -> bool:
            if i == 0:
                return False
            if p[j - 1] == '.':
                return True
            return s[i - 1] == p[j - 1]

        f = [[False] * (n + 1) for _ in range(m + 1)]
        f[0][0] = True
        for i in range(m + 1):# s
            for j in range(1, n + 1):# p
                if p[j - 1] == '*':
                    f[i][j] |= f[i][j - 2]  # 零次
                    if matches(i, j - 1):
                        f[i][j] |= f[i - 1][j]
                else:
                    if matches(i, j):
                        f[i][j] |= f[i - 1][j - 1]
        return f[m][n]

执行用时：48 ms
消耗内存：16.43 MB

参考来源：力扣官方题解