力扣刷题日记【2022/1/23】

10. 正则表达式匹配

给你一个字符串 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
解释：".” 表示可匹配零个或多个（’*’）任意字符（’.’）。

示例 4：
输入：s = “aab” p = “cab”
输出：true
解释：因为 ‘*’ 表示零个或多个，这里 ‘c’ 为 0 个, ‘a’ 被重复一次。因此可以匹配字符串 “aab”。

示例 5：
输入：s = “mississippi” p = “misisp*.”
输出：false

1. python自带库~（花里胡哨）

class Solution:
    def isMatch(self, s: str, p: str) -> bool:
        if re.fullmatch(p,s):
            return True
        return False

2. 动态规划
   我们用 f [ i ] [ j ] f[i][j] f[i][j] 表示 s 的前 i 个字符与 p 中的前 j 个字符是否能够匹配。在进行状态转移时，我们考虑 p 的第 j 个字符的匹配情况：

• 如果 p 的第 j 个字符是一个小写字母，那么我们必须在 s中匹配一个相同的小写字母，即
  f [ i ] [ j ] = { f [ i − 1 ] [ j − 1 ] , s [ i ] = p [ j ] false , s [ i ] ≠ p [ j ] f[i][j] = \begin{cases} f[i - 1][j - 1], & s[i] = p[j]\\ \text{false}, & s[i] \neq p[j] \end{cases} f[i][j]={f[i−1][j−1],false,​s[i]=p[j]s[i]​=p[j]​
• 字母 * 星号的组合在匹配的过程中，本质上只会有两种情况：
  • 匹配 s 末尾的一个字符，将该字符扔掉，而该组合还可以继续进行匹配；
  • 不匹配字符，将该组合扔掉，不再进行匹配。

如果按照这个角度进行思考，我们可以写出很精巧的状态转移方程：
f [ i ] [ j ] = { f [ i − 1 ] [ j ]  or  f [ i ] [ j − 2 ] , s [ i ] = p [ j − 1 ] f [ i ] [ j − 2 ] , s [ i ] ≠ p [ j − 1 ] ​ f[i][j] = \begin{cases} f[i - 1][j] \text{~or~} f[i][j - 2], & s[i] = p[j - 1] \\ f[i][j - 2], & s[i] \neq p[j - 1] \end{cases} ​ f[i][j]={f[i−1][j] or f[i][j−2],f[i][j−2],​s[i]=p[j−1]s[i]​=p[j−1]​​

在任意情况下，只要 p [ j ] p[j] p[j]是 “ . ” “.” “.” ，那么 p [ j ] p[j] p[j]一定成功匹配 s 中的任意一个小写字母。
最终的状态转移方程如下：
f [ i ] [ j ] = { if  ( p [ j ] ≠ “ ∗ ” ) = { f [ i − 1 ] [ j − 1 ] , s [ i ] = p [ j ]   o r   p [ j ] = “ . " false , otherwise otherwise = { f [ i − 1 ] [ j ]  or  f [ i ] [ j − 2 ] , s [ i ] = p [ j − 1 ]   o r   p [ j ] = “ . " f [ i ] [ j − 2 ] , otherwise f[i][j] = \begin{cases} \text{if~} (p[j] \neq “*”) = \begin{cases} f[i - 1][j - 1], & s[i]=p[j]~ or~ p[j]=“."\\ \text{false}, & \text{otherwise} \end{cases} \\ \text{otherwise} = \begin{cases} f[i - 1][j] \text{~or~} f[i][j - 2], & s[i]= p[j-1]~ or~ p[j]=“." \\ f[i][j - 2], & \text{otherwise} \end{cases} \end{cases} f[i][j]=⎩⎪⎪⎪⎪⎨⎪⎪⎪⎪⎧​if (p[j]​=“∗”)={f[i−1][j−1],false,​s[i]=p[j] or p[j]=“."otherwise​otherwise={f[i−1][j] or f[i][j−2],f[i][j−2],​s[i]=p[j−1] or p[j]=“."otherwise​​

class Solution:
    def isMatch(self, s: str, p: str) -> bool:
        s = " " + s
        dp = [[False]*(len(p)+1) for _ in range(len(s))]
        dp[0][0] = True

        for i in range(len(s)):
            for j in range(1, len(p)+1):
                if p[j-1] == '*':
                    dp[i][j] = dp[i][j-2] or dp[i-1][j] and (s[i]==p[j-2] or p[j-2]=='.')
                else:
                    dp[i][j] = dp[i-1][j-1] and (s[i]==p[j-1] or p[j-1]=='.')
        return dp[-1][-1]

——题解来自官方题解改编