题目描述

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

'.' 匹配任意单个字符
'*' 匹配零个或多个前面的那一个元素

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

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

题解

由于我一开始想当然了，所以一开始写的这些是针对于“星号代表匹配零个或多个任意字符，也就是a*可以代表a，可以代表ab，可以代表abb”情况下的题解。

对于串与模式的匹配，由于模式中的*与.对应多种匹配的可能性，因此首先想到了动态规划。dp[i][j]代表s[0…i]与p[0…j]能否匹配，为True或False。如果这样定义状态，那么让我们接下来考虑状态转移方程：

• 如果s[i]==p[j]，那么dp[i][j]=dp[i-1][j-1]。
• 如果p[j]==‘.’，那么可以匹配s[i]，dp[i][j]=dp[i-1][j-1]。
• 如果p[j]==‘*’，这是最难的一种情况。*可以匹配零个字符，或者任意多个重复字符，因此分两种情况：
  • 第一种情况，*匹配零个字符，也就是p[j]不参与匹配，即dp[i][j]=dp[i][j-1]。
  • 第二种情况，*匹配任意多个重复字符，那么必然需要s[i]==p[j-1]，因此向前遍历所有与s[i]相同字符的位置，假设匹配s[i-delta:i]，那么dp[i][j]=dp[i-delta-1][j-1]。则dp[i][j]=max(dp[i
• delta-1][j-1]) (delta>0)，并且保证s[i-delta]==s[i]。

之后，我们需要关注状态转移的顺序。dp[i][j]依赖于dp[i-1][j-1]、dp[i][j-1]、dp[i - delta][j-1]
(delta>0)，因此直接用两层for循环即可。

题目中的情况相对于上面的情况（也就是我想当然了的情况），有这样一些区别：

• ‘*’ 匹配零个或多个前面的那一个元素。也就是说"a星"可以是零个a、一个a、两个a…

以下部分与之前的保持一致：

• dp[i][j]代表s[0…i]能否匹配p[0…j]
• 如果s[i]==p[j]，那么这两个字符直接匹配，dp[i][j]=dp[i-1][j-1]。
• 如果p[j]==‘.’，那么不管s[i]是什么字符都可以匹配，dp[i][j]=dp[i-1][j-1]。

剩下的难点在于p[j]=='*'的情况。

由于p[j]如果为星号，那么只能取p[j-1]的字符进行重复零次或若干次，因此分为两种情况：要么星号代表零次（相当于去掉p[j-1]），要么星号代表重复p[j-1]若干次（此时必然有p[j-1]==s[i]）。这儿的两种情况为：

• 若p[j-1] != s[i]，那么这里的星号必然要代表重复零次，即去掉p[j-1]，因此dp[i][j] = dp[i][j-2]。
• 若p[j-1] == s[i] 或者 p[j-1] ==‘.’， 那么这个时候星号可以代表重复零次、一次或多次，对于下面的三种情况，只要有一种情况为True，结果就为True：
  • 情况1：
    abbbbbb
    ab*
    此时仍有很多很多的重复字符待匹配，先令dp[i][j]=dp[i-1][j]，相当于先匹配一个字符，后面的字符后面再看。
  • 情况2：
    ab
    ab*
    此时星号只需要重复前面的字符一次就可以了，也就是说星号有没有都一样，因此dp[i][j]=dp[i][j-1]。
  • 情况3：
    a
    aa*
    此时虽然星号所能重复的字符与s匹配上了，但还是不能重复多次（只能消去星号前面的字符），dp[i][j]=dp[i][j-2]。

以及补充一些编程时的技巧：

• 为了防止越界，我推荐dp数组多定义一个位置。即dp[i][j]代表s的前i个字符与p的前j个字符匹配。因此dp[0][0]=True。
• python定义二维数组dp[m][n]：
  dp = [[False] * n for _ in range(m)]
• 注意dp[i][j]对应s[i-1]与p[j-1]。
• for循环中的i与j是否要从0开始？i要，j可以不要！因为空字符可以与非空模式（如a*）匹配，但非空字符肯定不会与空模式匹配。

虽然代码行数很短，但这道题目的确很复杂。

代码

class Solution:
    def isMatch(self, s: str, p: str) -> bool:
        m, n = len(s) + 1, len(p) + 1
        dp = [[False] * n for _ in range(m)]
        dp[0][0] = True
        for i in range(0, 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]
                if p[j - 1] == '*':
                    if j >= 2 and s[i - 1] != p[j - 2]:
                        dp[i][j] = dp[i][j-2]
                    if j >= 2 and (s[i - 1] == p[j - 2] or p[j - 2] == '.'):
                        dp[i][j] = dp[i-1][j] or dp[i][j-1] or dp[i][j-2]
        return dp[m - 1][n - 1]