题目描述
给你一个字符串 s 和一个字符规律 p，请你来实现一个支持 '.' 和 '*' 的正则表达式匹配。
'.' 匹配任意单个字符
'*' 匹配零个或多个前面的那一个元素
所谓匹配，是要涵盖 整个 字符串 s的，而不是部分字符串。
说明:
s 可能为空，且只包含从 a-z 的小写字母。
p 可能为空，且只包含从 a-z 的小写字母，以及字符 . 和 *。
示例 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
思路：
- 递归
如何处理‘.’，任意匹配
如何处理“*”，不匹配，或者匹配多个前面的字符
容易超时 - 动态规划
通过注释解释
class Solution:
def isMatch(self, text, pattern):
if not pattern:
return not text
first = text and pattern[0] in [text[0], "."]
if len(pattern) >= 2 and pattern[1] == "*":
return self.isMatch(text, pattern[2:]) or (first and self.isMatch(text[1:], pattern))
return first and self.isMatch(text[1:], pattern[1:])
动态规划代码：
class Solution:
'''
给定一个字符串 (s) 和一个字符模式 (p)。实现支持 '.' 和 '*' 的正则表达式匹配。
'.' 匹配任意单个字符。
'*' 匹配零个或多个前面的元素。
匹配应该覆盖整个字符串 (s) ，而不是部分字符串。
s 可能为空，且只包含从 a-z 的小写字母。
p 可能为空，且只包含从 a-z 的小写字母，以及字符 . 和 *
参考: https://blog.csdn.net/hk2291976/article/details/51165010
'''
def isMatch(self, s: str, p: str) -> bool:
'''
p.charAt(j) == s.charAt(i) : dp[i][j] = dp[i-1][j-1]
If p.charAt(j) == '.' : dp[i][j] = dp[i-1][j-1];
If p.charAt(j) == '*': here are two sub conditions:
//in this case, a* only counts as empty, otherwise is not match
- if p.charAt(j-1) != s.charAt(i) : dp[i][j] = dp[i][j-2]
- if p.charAt(j-1) == s.charAt(i) or p.charAt(i-1) == '.':
dp[i][j] = dp[i-1][j] //in this case, a* counts as multiple a
dp[i][j] = dp[i][j-1] // in this case, a* counts as single a
dp[i][j] = dp[i][j-2] // in this case, a* counts as empty
思路: 动态规划, 沿着匹配串和字符串构成矩阵的对角线传递状态
1. 状态矩阵的首行与首列对应于空字符与空匹配符
2. 对角线意味着匹配串是否匹配对应的字符串
'''
ns = len(s)
np = len(p)
dp = [[False] * (np + 1) for _ in range(ns + 1)]
dp[0][0] = True
# 匹配空字符串的情况, 匹配串为空时已经为False, 不再更新
for i in range(np):
# 根据规则, *前必存在一个字符, 则当前为*时, 其状态与前2的状态一致
if p[i] == '*' and dp[0][i - 1]:
dp[0][i + 1] = True
# 更新状态矩阵
for i in range(1, ns + 1):
for j in range(1, np + 1):
# i,j是矩阵的行与列, 对应到匹配串和字符串的索引要-1
# 匹配串与字符串匹配(相等或为.)传递状态
if p[j - 1] == s[i - 1] or p[j - 1] == '.':
dp[i][j] = dp[i - 1][j - 1]
# 匹配串中 * 字符特殊处理
elif p[j - 1] == '*':
# 根据匹配规则, 比较匹配串*的前一个字符与字符串中前一个字符
# 二者不相等时, a*只有作为空字符串时才可能匹配,
# 这就是说, 略过前一个字符, *字符对应的状态与字符串中前2个字符的状态一致
if p[j - 2] != s[i - 1]:
dp[i][j] = dp[i][j - 2]
# 二者相等时有三种情况
# a*作为: 空字符, 单字符 a, 多字符 aaa...
if p[j - 2] == s[i - 1] or p[j - 2] == '.':
dp[i][j] = dp[i][j - 2] or dp[i][j - 1] or dp[i - 1][j]
return dp[ns][np]
AC10动态规划
