题目描述
给了一个字符串s和字符规律p
其中p可能含有"."和"","."可以匹配任何单个字符，""需要和前面字符结合，表示匹配0-任意个前面字符
问给定的p能不能匹配s
| f1-序列dp |
基本分析
1.怎么定义状态？dp[i][j]表示p的前j个字符能不能匹配s的前i个字符
2.对i分类还是对j分类？j有3种情况，对j分类
- p[j]是字符，要能转移需要有dp[i-1][j-1]能匹配，s[i]=p[j]
- p[j]是"."， 要能转移需要有dp[i-1][j-1]能匹配，p[j]是'.'
- p[j]是"*", 需要结合前面一个字符考虑，可能能匹配0个，1个，多个，这个可能是无限的，这个题的难点就在这里
3.怎么推导出来p[j]是"*"的表达式？
- 枚举f[i][j]成立时匹配0、1、2、。。。k时的表达式
- 将i替换为i-1，得到f[i-1][j]时候的表达式
- 分析以上表达式关系，得到f[i][j] = f[i][j-2] 或 (f[i-1][j] 且 p[j-1]能匹配s[i])
4.定义状态的时候有啥细节？
- 预处理：在原字符插空格，（1）为了能直接用i和j表达第几个；（2）可以把f[0][0]=True的结果滚下去
- 开数组：开到[n+1][m+1]
- f[0][0] = True
5.转移的时候的细节？
- 遍历时候，对s是range(0, n+1),需要考虑匹配0；对p是(1,m+1)
- p[j]的后面接"*"时，要一起考虑，需要pass
- p[j]是字符或者"*"时，可以一起考虑，但因为有i-1的转移，需要判断i的越界情况
- p[j]是"*"时，按照转移关系来，需要判断j的越界情况，i的越界情况，p[j-1]能匹配s[i]的情况
代码
class Solution:
def isMatch(self, s: str, p: str) -> bool:
n, m = len(s), len(p)
# 头插空格的原因？
s = ' ' + s
p = ' ' + p
f = [[False] * (m+1) for _ in range(n+1)]
f[0][0] = True
for i in range(n+1):
for j in range(1, m+1):
# 如果后面是*表示不能单独使用，跳过
if j+1 <= m and p[j+1]=="*":
continue
# 考虑为普通字符或者"."
if i-1 >=0 and p[j] !="*":
f[i][j] = f[i-1][j-1] and (s[i]==p[j] or p[j]==".")
elif p[j] == "*":
f[i][j] = (j-2>=0 and f[i][j-2]) or (i-1>=0 and f[i-1][j] and (s[i]==p[j-1] or p[j-1]=="."))
return f[n][m]
复杂度
时间：共计\(n \cdot m个状态， O(n \cdot m)\)
空间：\(O(n \cdot m)\)
总结
第1个难点是状态定义的写法，需要两个维度i和j，来表示前j匹配前i的情况
第2个难点在于考虑转移时对谁进行分类？这里是j，题目给了3个情况
第3个难点是具体考虑怎么转移？对p[j]取非"*"的时候，按照之前的定义，可以解决了，但是对于"*"的情况，可以匹配0、1、2、...n, 这样写or太长了，怎么处理？题目的做法是用了换元法，先写成[i][j]的情况，再写[i-1][j]的情况，然后发现可以把无限的式子化为有限
第4个难点是状态定义的细节，为了转移f[0][0],用了头插空格
第5个注意点是转移的时候，需要往前去翻，这个时候不管对i还是j，都要先保证不越界