0010. 正则表达式匹配

0010. 正则表达式匹配 #

  • 标签:递归、字符串、动态规划
  • 难度:困难

题目大意 #

描述:给定一个字符串 s 和一个字符模式串 p

要求:实现一个支持 '.''*' 的正则表达式匹配。两个字符串完全匹配才算匹配成功。如果匹配成功,则返回 True,否则返回 False

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

说明

  • $1 \le s.length \le 20$。
  • $1 \le p.length \le 30$。
  • s 只包含从 a ~ z 的小写字母。
  • p 只包含从 a ~ z 的小写字母,以及字符 .*
  • 保证每次出现字符 * 时,前面都匹配到有效的字符。

示例

1
2
3
4
5
6
7
输入s = "aa", p = "a*"
输出True
解释因为 '*' 代表可以匹配零个或多个前面的那一个元素, 在这里前面的元素就是 'a'因此字符串 "aa" 可被视为 'a' 重复了一次

输入s = "aa", p = "a"
输出False
解释"a" 无法匹配 "aa" 整个字符串

解题思路 #

思路 1:动态规划 #

1. 划分阶段 #

按照两个字符串的结尾位置进行阶段划分。

2. 定义状态 #

定义状态 dp[i][j] 表示为:字符串 s 的前 i 个字符与字符串 p 的前 j 个字符是否匹配。

3. 状态转移方程 #
  • 如果 s[i - 1] == p[j - 1],则字符串 s 的第 i 个字符与字符串 p 的第 j 个字符是匹配的。此时「字符串 s 的前 i 个字符与字符串 p 的前 j 个字符是否匹配」取决于「字符串 s 的前 i - 1 个字符与字符串 p 的前 j - 1 个字符是否匹配」。即 dp[i][j] = dp[i - 1][j - 1]
  • 如果 p[j - 1] == '.',则字符串 s 的第 i 个字符与字符串 p 的第 j 个字符是匹配的(同上)。此时 dp[i][j] = dp[i - 1][j - 1]
  • 如果 p[j - 1] == '*',则我们可以对字符 p[j - 2] 进行 0 ~ 若干次数的匹配。
    • 如果 s[i - 1] != p[j - 2] 并且 p[j - 2] != '.',则说明当前星号匹配不上,只能匹配 0 次(即匹配空字符串),则「字符串 s 的前 i 个字符与字符串 p 的前 j 个字符是否匹配」取决于「字符串 s 的前 i 个字符与字符串 p 的前 j - 2 个字符是否匹配」,即 dp[i][j] = dp[i][j - 2]
    • 如果 s[i - 1] == p[j - 2] 或者 p[j - 2] == '.',则说明当前星号前面的字符 p[j - 2] 可以匹配 s[i - 1]
      • 如果匹配 0 个,则「字符串 s 的前 i 个字符与字符串 p 的前 j 个字符是否匹配」取决于「字符串 s 的前 i 个字符与字符串 p 的前 j - 2 个字符是否匹配」。即 dp[i][j] = dp[i][j - 2]
      • 如果匹配 1 个,则「字符串 s 的前 i 个字符与字符串 p 的前 j 个字符是否匹配」取决于「字符串 s 的前 i 个字符与字符串 p 的前 j - 1 个字符是否匹配」。即 dp[i][j] = dp[i][j - 1]
      • 如果匹配多个,则「字符串 s 的前 i 个字符与字符串 p 的前 j 个字符是否匹配」取决于「字符串 s 的前 i - 1 个字符与字符串 p 的前 j 个字符是否匹配」。即 dp[i][j] = dp[i - 1][j]
4. 初始条件 #
  • 默认状态下,两个空字符串是匹配的,即 dp[0][0] = True
  • 当字符串 s 为空,字符串 p 右端有 * 时,想要匹配,则如果「空字符串」与「去掉字符串 p 右端的 ** 之前的字符之后的字符串」匹配的话,则空字符串与字符串 p 匹配。也就是说如果 p[j - 1] == '*',则 dp[0][j] = dp[0][j - 2]
5. 最终结果 #

根据我们之前定义的状态, dp[i][j] 表示为:字符串 s 的前 i 个字符与字符串 p 的前 j 个字符是否匹配。则最终结果为 dp[size_s][size_p],其实 size_s 是字符串 s 的长度,size_p 是字符串 p 的长度。

思路 1:动态规划代码 #

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution:
    def isMatch(self, s: str, p: str) -> bool:
        size_s, size_p = len(s), len(p)
        dp = [[False for _ in range(size_p + 1)] for _ in range(size_s + 1)]
        
        dp[0][0] = True
        for j in range(1, size_p + 1):
            if p[j - 1] == '*':
                dp[0][j] = dp[0][j - 2]

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

        return dp[size_s][size_p]

思路 1:复杂度分析 #

  • 时间复杂度:$O(m n)$,其中 $m$ 是字符串 s 的长度,$n$ 是字符串 p 的长度。使用了两重循环,外层循环遍历的时间复杂度是 $O(m)$,内层循环遍历的时间复杂度是 $O(n)$,所以总体的时间复杂度为 $O(m n)$。
  • 空间复杂度:$O(m n)$,其中 $m$ 是字符串 s 的长度,$n$ 是字符串 p 的长度。使用了二维数组保存状态,且第一维的空间复杂度为 $O(m)$,第二位的空间复杂度为 $O(n)$,所以总体的空间复杂度为 $O(m n)$。
本站总访问量  次  |  您是本站第  位访问者