给定一个字符串 (s) 和一个字符模式 (p) ，实现一个支持 '?' 和 '*' 的通配符匹配。
'?' 可以匹配任何单个字符。
'*' 可以匹配任意字符串（包括空字符串）。两个字符串完全匹配才算匹配成功。
说明:
s可能为空，且只包含从a-z的小写字母。p可能为空，且只包含从a-z的小写字母，以及字符?和*。
示例 1:
输入:
s = "aa"
p = "a"
输出: false
解释: "a" 无法匹配 "aa" 整个字符串。示例 2:
输入:
s = "aa"
p = "*"
输出: true
解释: '*' 可以匹配任意字符串。示例 3:
输入:
s = "cb"
p = "?a"
输出: false
解释: '?' 可以匹配 'c', 但第二个 'a' 无法匹配 'b'。示例 4:
输入:
s = "adceb"
p = "*a*b"
输出: true
解释: 第一个 '*' 可以匹配空字符串, 第二个 '*' 可以匹配字符串 "dce".示例 5:
输入:
s = "acdcb"
p = "a*c?b"
输出: false思路：回溯算法（N叉树）
# @lc code=start
class Solution:
def isMatch(self,s: str, p: str) -> bool:
if s=="" and p=="":
return True
if p=="":
return False
len1=len(s)
n1=0
m1=""
len2=len(p)
for i in range(1,len2):
if p[i]=="*" and p[i-1]=="*":
continue
else :
m1=m1+p[i-1]
n1=1+n1
p=m1+p[-1]
len2=len(p)
def submacth(i,j):
if i==len1 and j==len2:
return True
if j==len2:
return False
if i==len1 and (p[j:]!="*"*len(p[j:])):
#print(False)
return False
if p[j]!="*" :
if p[j]=="?"or p[j]==s[i]:
i=i+1
j=j+1
return submacth(i,j)
else:
#print(False)
return False
if p[j]=="*" and j==len2-1:
#print("3333")
l=len1
h=len2
return submacth(l,h)
if p[j]=="*" and j<len2-1:
for m in range(i,len1):
if s[m]==p[j+1] or p[j+1]=="?":
#print(m,j+1,"hh")
l=m+1
h=j+2
if submacth(l,h):
return True
return False
return submacth(0,0)
需改进：
动态规划步骤：
- 确定dp[i][j]状态含义
- 确定 状态转移方程
- 确定dp初始值
参考官方题解：动态规划问题dp[i][j]表示s的前i个字符和 p的前j个字符是否匹配。在进行状态转移时，我们可以考虑模式 p 的第 j 个字符 pj，与之对应的是字符串 s 中的第 i 个字符si：
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(1, n + 1):
if p[i - 1] == '*':
dp[0][i] = True
else:
break
for i in range(1, m + 1):
for j in range(1, n + 1):
if p[j - 1] == '*':
dp[i][j] = dp[i][j - 1] | dp[i - 1][j]
elif p[j - 1] == '?' or s[i - 1] == p[j - 1]:
dp[i][j] = dp[i - 1][j - 1]
return dp[m][n]