https://leetcode-cn.com/problems/regular-expression-matching/
这里要注意的是“*”表示前面的字符可以重复0到无数次，并不是传统意义上的通配符。
把X*（X为任意字符），当做一个整体，这是最难处理的部分，因为x可以重复0到无数次:
- 出现0次：s不变，p跳过
X*部分，右移两位：isMatch(s, p[2:]) - 出现1~n次：s与p匹配一次（first_match），且s右移一位，p不变（保持
X*）：first_match and isMatch(s[1:], p)
class Solution:
def isMatch(self, s: str, p: str) -> bool:
if not p:
return not s
#为了使代码简洁，第一位字符匹配的结果用first_match代替
#首先s不能为空，然后看第0位是否相等，或者p第0位是否为'.'
first_match = bool(s) and (s[0] == p[0] or p[0] == '.')
#处理'X*'字段
if len(p) >= 2 and p[1] == '*':
return self.isMatch(s, p[2:]) or \ #'X*'出现0次
(first_match and self.isMatch(s[1:], p)) #'X*'出现n次
#常规匹配
else:
return first_match and self.isMatch(s[1:], p[1:])用二维矩阵dp记录，dp[i][j]的布尔值表示s[0..i)是否与p[0..j)匹配（注意右边是开区间），初始值为False。
初始状态：令dp[0][0]为true，i=0表示s为空，j=0表示p为空，s、p都为空的时候是匹配的。
重点还是处理X*类型的p串：
情况1）：判断“a”和“ab*”是否匹配
s=“a” ， i=1（注意前面表述是开区间）
^
p=“a b *” ， j=3
^
b*匹配0次，则j回退两位，i不动：
s=“a” ， i=1
^
p=“a b *” ， j=1
^
若“a”和“a”匹配，则“a”和“ab*”匹配。
即dp[i][j]的状态和dp[i][j-2]是相同的，推导得dp[i][j] = dp[i][j-2]
情况2）：判断“abb...”和“ab*”是否匹配
s=“a b b...” ， i=2
^
p=“a b *” ， j=3
^
b*匹配1~n次，则i回退1位，j回退2位
s=“a b b...” ， i=1
^
p=“a b *” ， j=1
^
若“a”和“a”匹配，且“a”和“ab*_”_匹配，则“ab”和“ab*”匹配。
“a”和“a”匹配的条件为：s[i-1] == p[j-2] ,或p[j-2] == ‘.’（单个字符匹配）
“a”和“ab*”匹配的条件：有点抽象，因为b可以匹配0到无数个b，因此要保证上一个状态是匹配的（模式串p不动；s串回退一位，类似递归中的情况2），当前状态才能匹配。上一个状态为：dp[i-1][j] = true 综上，a匹配一次的条件：
dp[i-1][j] and (s[i-1] == p[j-2] or p[j-2] == '.')
情况1）和2）是并列的。
情况3）：单个字符匹配：
两种，一种是相等匹配，另一种是‘.’匹配。而且上一个状态dp[i-1][j-1]匹配
条件：
dp[i-1][j-1] and (s[i-1] == p[j-1] or p[j-1] == '.')
此外还要注意下标，要保证i>0
因为有p[j-1] == ‘*’的限制，因此j不用过多限制，且根据题意，’*‘之前一定有东西，len(p)>=2
从0到m ，j从1到n，因为j=0时p为空串，除了空以外的所有s都不匹配
class Solution:
def isMatch(self, s: str, p: str) -> bool:
m, n = len(s), len(p)
dp = [[False] * (n+1) for _ in range(m+1)]
dp[0][0] = True
for i in range(m+1):
for j in range(1, n+1):
if p[j-1] == '*':
dp[i][j] = dp[i][j-2] or (i>0 and dp[i-1][j] and ((s[i-1] == p[j-2]) or p[j-2] == '.'))
else:
dp[i][j] = i>0 and dp[i-1][j-1] and (s[i-1] == p[j-1] or p[j-1] == '.')
return dp[m][n]