难度: Hard
给你一个字符串 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 <= 201 <= p.length <= 20s 只包含从 a-z 的小写字母。p 只包含从 a-z 的小写字母，以及字符 . 和 *。* 时，前面都匹配到有效的字符运行时间: 40 ms
内存: 15.3 MB
class Solution:
def isMatch(self, s: str, p: str) -> bool:
m = len(s)
n = len(p)
memo = dict()
def dp(i, j):
if j == n:
return i == m
if i == m:
if len(p[j:]) % 2 == 1:
return False
else:
while j+1 < n:
if p[j+1] != '*':
return False
j += 2
return True
if (i, j) in memo:
return memo[(i, j)]
if s[i] == p[j] or p[j] == '.':
if j+1 < n and p[j+1] == '*':
res = dp(i+1, j) or dp(i, j+2)
else:
res = dp(i+1, j+1)
else:
if j+1 < n and p[j+1] == '*':
res = dp(i, j+2)
else:
res = False
memo[(i, j)] = res
return res
return dp(0, 0)
这个题解采用递归和记忆化搜索的方法来解决正则表达式匹配问题。递归函数dp(i, j)表示字符串s的前i个字符和模式串p的前j个字符是否匹配。首先处理一些边界情况，如模式串p匹配完毕或字符串s匹配完毕。然后利用记忆化搜索避免重复计算子问题。接着根据当前字符是否匹配以及模式串的下一个字符是否为'*'来分情况递归，最终返回是否匹配的结果。
时间复杂度: O(m*n)
空间复杂度: O(m*n)
class Solution:
def isMatch(self, s: str, p: str) -> bool:
m = len(s)
n = len(p)
memo = dict()
def dp(i, j):
if j == n:
# 模式串p匹配完毕，需要字符串s也匹配完毕
return i == m
if i == m:
# 字符串s匹配完毕，需要检查模式串p的剩余部分是否合法
if len(p[j:]) % 2 == 1:
return False
else:
while j+1 < n:
if p[j+1] != '*':
return False
j += 2
return True
if (i, j) in memo:
# 如果已经计算过该子问题，直接返回结果
return memo[(i, j)]
if s[i] == p[j] or p[j] == '.':
if j+1 < n and p[j+1] == '*':
# 如果当前字符匹配且下一个字符为'*'，可以匹配多个字符或跳过'*'
res = dp(i+1, j) or dp(i, j+2)
else:
# 如果当前字符匹配但下一个字符不为'*'，继续匹配下一个字符
res = dp(i+1, j+1)
else:
if j+1 < n and p[j+1] == '*':
# 如果当前字符不匹配但下一个字符为'*'，只能跳过'*'
res = dp(i, j+2)
else:
# 如果当前字符不匹配且下一个字符不为'*'，匹配失败
res = False
memo[(i, j)] = res
return res
return dp(0, 0)
'.'字符可以匹配任意单个字符，'*'字符可以匹配零个或多个前面的那一个元素。在递归中，'.'用于匹配当前字符，'*'用于处理匹配多个字符或跳过'*'的情况。
即使字符串s已经匹配完毕，但模式串p可能还有剩余部分。需要检查剩余部分是否能够匹配空字符串，以确保整个模式串p都能被合法匹配。
因为'*'可以匹配零个或多个前面的元素，所以即使当前字符匹配成功，也需要考虑'*'的情况，以处理匹配多个字符或跳过'*'的可能性。
通过使用一个字典（或哈希表）来存储已经计算过的子问题的结果，从而避免重复计算。这种方法称为记忆化搜索。
时间复杂度是通过分析算法执行的时间随输入数据规模增长的变化趋势来计算的。空间复杂度是通过分析算法在执行过程中占用的内存空间随输入数据规模增长的变化趋势来计算的。在这个题解中，时间复杂度和空间复杂度都是O(m*n)，其中m和n分别是字符串s和模式串p的长度。