44. 通配符匹配
方法一：
动态规划
动态规划：dp[i][j]表示：s的前i个字符与p的前j个字符是否匹配
状态转移方程
如果s1的第 i 个字符和s2的第 j 个字符相同，或者s2的第 j 个字符为 “?”
f[i][j] = f[i - 1][j - 1]
如果s2的第 j 个字符为 *
若s2的第 j 个字符匹配空串, f[i][j] = f[i][j - 1]
若s2的第 j 个字符匹配s1的第 i 个字符, f[i][j] = f[i - 1][j]
class Solution:
def isMatch(self, s: str, p: str) -> bool:
plen = len(p)
slen = len(s)
dp = [ [False]*(plen+1) for _ in range(slen+1)]
# 先将dp数组的第0行和第0列初始化
# 下面是初始化dp[i][0]显然都是False，所以不用初始化
# dp[0][0]显然是True
dp[0][0] = True
# 下面是初始化dp[0][j]
for j in range(1,plen+1):
dp[0][j] = dp[0][j-1] and p[j-1]=='*'
for i in range(1,slen+1):
for j in range(1,plen+1):
if s[i-1]==p[j-1] or p[j-1]=='?':
dp[i][j] = dp[i-1][j-1]
elif p[j-1]=='*':
dp[i][j] = dp[i][j-1] or dp[i-1][j]
return dp[slen][plen]
方法二：回溯
我实在没看懂
