ericpuwang

正则表达式匹配

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

题解

• 状态定义: dp[i][j]表示s的前i个字符和p的前j个字符能否匹配
• 状态转移: dp[0][0]代表的是空字符的状态,因此dp[i][j]对应的字符s[i-1]和p[j-1]
  • 当p[j-1] != '*'时: \(dp[i][j] = \begin{cases} dp[i-1][j-1], s[i]=p[j] \\ False, s[i] \neq p[j] \end{cases}\)
  • 当p[j-1] = '.'时: dp[i][j] = dp[i-1][j-1]
  • 当p[j-1] == '*'时, 表示可对p[j]的前一个字符p[j−1]匹配(或理解为复制)任意次(包括0次)
    • 匹配零次: dp[i][j] = dp[i][j-2]
    • 匹配一次: 若s[i]=p[j-1],则dp[i][j]可由dp[i-1][j-2]转移而来,此时有: dp[i][j] = dp[i-1][j-2] && s[i]=p[j-1]
    • 匹配k次: 若s[i-k+1,...,i]=p[j-1],则有:dp[i][j] = dp[i-k][j-2] && s[i-k+1,...,i]=p[j-]
• 转移方程: \(dp[i][j] = \begin{cases} dp[i-1][j-1], s[i]=p[j] 或 p[j]='.' \\ dp[i][j-2], p[j]='*' \\ dp[i][j-2] 或 dp[i-1][j], p[j]='*'且(s[i]=p[j-1]或p[j-1]='.') \end{cases}\)
• 方程初始化:
  • dp[0][0]=True
  • 对于其他dp[0][j]
    • p[j]='*'时,则有dp[0][j]=dp[0][j−2]
    • 反之. s[0,...,j]无法与空字符匹配,因此有dp[0][j]=False

class Solution:
    def isMatch(self, s: str, p: str) -> bool:
        m, n = len(s) + 1, len(p) + 1
        # 为便于状态更新,减少对边界的判断,初始二维dp数组维度为(m+1)×(n+1)
        # 其中第一行和第一列的状态分别表示字符串s和p为空时的情况。
        dp = [[False] * n for _ in range(m)]
        dp[0][0] = True # 标识两个空字符串能够匹配
        for j in range(1, n):
            if p[j-1] == '*':
                dp[0][j] = dp[0][j-2]

        for i in range(1, m):
            for j in range(1, n):
                if s[i-1] == p[j-1] or p[j-1] == '.':
                    dp[i][j] = dp[i-1][j-1]
                elif p[j-1] == '*': # 首字符不为*,则此处j>=2
                    dp[i][j] = dp[i][j-2] # *号复制前面字符零次
                    if s[i-1] == p[j-2] or p[j-2] == '.': # *号复制前面字符k(k>0)次
                        dp[i][j] |= dp[i-1][j]

        return dp[-1][-1]