1. 解题前的思考
一开始拿到这题，其实还挺懵逼的。🤣如果这题没有 ‘*’ （后面统一称呼为"星号”）这个字符在正则表达式中，这题将会简单点，我们只需要从左往右遍历字符串 看是否能跟 模式 '.' 匹配上即可。
无星号的正则表达式匹配代码部分：
def match(self, str, pattern):
if not pattern: return not str
first_match = bool(str) and pattern[0] in {str[0], '.'}
return first_match and self.match(str[1:], pattern[1:])但是现在有这个星号，我们就需要考虑 字符串的很多不同后缀， 看他们能否都跟 模式匹配上。而递归
就是一种很直接解决这样问题的方法。
2. 递归（Recursion）解题思路
2.1 回顾一：什么问题可以用递归解决？
- 主问题可以拆分为多个子问题；
- 主问题和子问题的解题思路一致；
- 存在终止条件。
2.2 回顾二：递归问题如何解决？
- 找到递推公式；
- 找到终止条件；
- 将他们翻译成代码。
2.3 “正则表达式匹配”的递归图解思路
- 首先我们来找相对简单的终止条件（也就是pattern长度只有一位的情况下的正则匹配），先看下面三个示例：
到这里可以发现，只有str[0] = pattern[0] 时，才会正则匹配。所以它就是我们要找的终止条件first_match，接下来我们再看递归公式应该如何推导出来。
递推公式
第一种：len(pattern) = 2 且 pattern[1] = '*'，还是先看三个示例：
发现没，这三个示例里，只有当first_match 存在，并且 str[1] = pattern[1]的时候，正则匹配才会True；否则就是False。第二种：len(pattern) > 2 且 pattern[1] = '*'，此时的正则匹配会出现如下几种示例：
这三个示例能推导出的公式跟 第一种是几乎一样的！只是第二个条件变成 str[1:] = pattern才成立。
这里还有另一种示例：
该示例向我们展示了另一种匹配为True的规则，就是 str = pattern[2:] 的情况。第三种：len(pattern) > 2 且 pattern[1] <> '*'，星号在索引1之后的任意位置，首先看一个False案例：
之所以str（'aaa'）与pattern（'ab*a')不匹配，是因为当pattern的星号和前面的b字符存在0个匹配 时，str只有头两个字符能跟pattern匹配上，但是第三个就无法匹配，上图就会变成👇下图这样：
而星号与前面的b字符存在 1个匹配时，就更匹配不上字符串 ‘aaa’：
再看一个True 案例：
首先首位匹配上了，当第一个星号和第二个星号都与前面的字符 0 匹配的时候，上面的案例就可以变形如下：
可以发现此时的pattern是存在与字符串str('aaa') 正则匹配的情况。此刻的匹配规则就变成首先first_match, 并且str[1:]要与pattern[1:]才行。
3. 核心代码
class Solution:
def match(self , str , pattern ):
if not pattern: #1.特殊情况，不存在匹配模式，那么就没有匹配字符串
return not str
#2. 递归的终止条件f(1) = 1：在这里就是 首位即匹配。
first_match = str and pattern[0] in {str[0], '.'}
#如果模式长度 >= 2,并且 模式索引[1] == '*'情况，也要分两种：
if len(pattern) >= 2 and pattern[1] == '*':
#第一种就是模式长度>2的情况下：字符串完全匹配从模式索引2之后的位置
return (self.match(str, pattern[2:]) or
#或者模式长度 =2的情况下：字符串从索引1位置开始，完全匹配模式
first_match and self.match(str[1:], pattern))
else:
#否则，模式长度>=2,而模式索引从1开始是 点字符或 *字符在其他位置，
return first_match and self.match(str[1:], pattern[1:])4. 复杂度分析
- 时间复杂度：O(m*n)(m，n分别代表计算str和pattern的长度所需时间）
- 空间复杂度：O(m*n)(即存储str和pattern所需空间）
--------------------------------------------解法二的分割线--------------------------------------------------------
5. 动态规划的解法
5.1 解题思路
根据上面的递归解法，可以发现此题还能用动态规划来解，那么解题思路就是先找到动态转移方程，再转化为代码。
5.2 图解示例
就以上面的最后一个案例进行动态规划的图解：
- 首先我们定义一个f[i][j]的状态转移方程，其中i 表示str中的第i个字符；j表示pattern中的第j个字符，然后判断是否匹配。
- 接着我们需要判断两种情况，第一种是当i、j指向的字符是同一个字母/点号（"."）的时候，我们只需要判断对应位置的字符是否相同，相同则转移状态去判断子问题f[i-1][j-1]是否匹配，如下图所示：
此时可以得到状态转移方程的第一部分： - 然后当 j 为"*"的时候 ，可以把 b* 和 c* 这样的看作一个整体:
然后有两种子问题的情况，第一种是b*匹配完 a 后，继续使用：
此时的转移方程就是 f[i-1][j]；
第二种就是b*匹配完a后，就舍弃：
此时的转移方程为：f[i][j-2]。
5.3 核心代码
#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
#
# @param str string字符串
# @param pattern string字符串
# @return bool布尔型
#
class Solution:
def match(self , str , pattern ):
m, n = len(str), len(pattern) # 分别找到str和pattern的长度
def matches(i, j): #定义一个转移方程函数
if i == 0: #首先考虑一种特殊情况： str为空；
#否则第一种是当i、j指向的字符是同一个字母/点号（"."）的时候，我们只需要判断对应位置的字符是否相同，
#相同则转移状态去判断子问题f[i-1][j-1]是否匹配
return False
if pattern[j - 1] == '.':
return True
return str[i - 1] == pattern[j - 1]
f = [[False] * (n + 1) for _ in range(m + 1)]
f[0][0] = True #动态规划的边界条件为f[0][0]=true，即两个空字符串是可以匹配的
for i in range(m + 1):
for j in range(1, n + 1):
#判断当j 指向 * 号的时候两种情况：
if pattern[j - 1] == '*':
f[i][j] |= f[i][j - 2]
if matches(i, j - 1):
f[i][j] |= f[i - 1][j]
else:
if matches(i, j):
f[i][j] |= f[i - 1][j - 1]
return f[m][n]5.4 复杂度分析
时间复杂度：O(mn)（其中 m 和 n分别是字符串str 和 pattern 的长度。）
空间复杂度：O(mn)（即为存储所有状态使用的空间。）
京公网安备 11010502036488号