10. 正则表达式匹配

Difficulty
Hard
Tags
动态规划
URL
https://leetcode.cn/problems/regular-expression-matching/
Star
给你一个字符串 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 <= 30
  • s 只包含从 a-z 的小写字母。
  • p 只包含从 a-z 的小写字母，以及字符 . 和 。
  • 保证每次出现字符 时，前面都匹配到有效的字符
通过次数311,548提交次数984,011

法1 动态规划

思路
动态规划 双序列型
dp[i][j]表示子串 s[0:i+1]和子模式 p[0:j+1]能否匹配成功。考虑以下三种情况：
  • if s[i] == p[j] or p[j] == ".", dp[i][j] = dp[i-1][j-1] ,转为为了子问题
  • if p[j] == "*", 此时可以两方面考虑：
    • * 代表前一个字符p[j-1]出现了 0 次，那么p[j-1] 和 p[j] 两个字符相当于没有出现过，可转为子问题 dp[i][j] = dp[i][j-2]
    • * 代表前一个字符p[j-1]出现 n (n ≥ 1)次 且s[i]是最后一个，此时必须满足 s[i] == p[j-1] or p[j-1] == "."，然后把问题转化为子问题 dp[i][j] = dp[i-1][j]
题解
class Solution:
    def isMatch(self, s: str, p: str) -> bool:
        s = "#" + s
        p = "#" + p

        dp = [[False] * len(p) for _ in range(len(s))]
        dp[0][0] = True

        for j in range(1, len(dp[0])):
            if p[j] != "*":
                dp[0][j] = False
            else:
                dp[0][j] = dp[0][j-2] if j - 2 >= 0 else True

        for i in range(1, len(dp)):
            for j in range(1, len(dp[0])):
                if s[i] == p[j] or p[j] == ".":
                    dp[i][j] = dp[i-1][j-1]
                else:
                    if p[j] == "*":
                        if j >= 2:
                            dp[i][j] = dp[i][j] or dp[i][j-2]
                        if p[j-1] == s[i]  or p[j-1] == ".":
                            dp[i][j] = dp[i][j] or dp[i-1][j]

        return dp[-1][-1]