44.通配符匹配题目来源：力扣（LeetCode）https://leetcode-cn.com/problems/wildcard-matching题目给定一个字符串（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解题思路：动态规划问题类似于10.正则表达式匹配。关于[10.正则表达式匹配]，你可以通过以下链接阅读理解：LeetCode10.正则表达式匹配|Python但是这里的两个问题还是有一些区别的。[10。正则表达式匹配】本题字符模式p的字符不是独立的，例如：.*两者组合会形成一个新的匹配模式。本题中p的字符是独立的，不会与前后关联。先看题目描述，其中字符模式p，有以下几种情况：a-z小写字母，这里只对应对应的小写字母？，可以匹配任意单个字符（即任意字母）*，匹配任意字符串（包括空字符串，即可以匹配0个或多个字符）这道题使用了动态规划的解法，先定义状态，用dp[i][j]表示s的前i个字符串和patternp是否匹配前j个字符串。那么在状态转移的时候，会遇到如下情况：如果p[j-1]==s[i-1]或者p[j-1]=='?'，则表示当前第i个字符被匹配，则dp[i][j]可以从dp[i-1][j-1]转换而来。如果p[j-1]=='*'，表示当前可以匹配0个或多个字符。那么dp[i][j]可以从dp[i][j-1]或dp[i-1][j]转移。具体情况如下：当使用星号匹配时，dp[i][j]可由dp[i-1][j]转入不使用星号匹配时，dp[i][j]可由dp转入[i][j-1]被转移。因此，状态转移方程如下：现在进行初始化，但是这里需要注意边界问题：初始化dp[0][0]=True，即当字符串s和字符模式p为空时，表示可以匹配；dp[i][0]表示字符模式p为空，不能匹配非空字符串，这里必须为False；（初始dp为False）这里的dp[0][j]表示字符模式p不为空，匹配空串。这里只有字符模式的前j个字符是星号*才能成立，所以也需要根据情况单独初始化。具体代码实现如下。代码实现类解决方案：defisMatch(self,s:str,p:str)->bool:s_length=len(s)p_length=len(p)#初始化dpdp=[[False]*(p_length+1)for_inrange(s_length+1)]#初始化dp[0][0],表示空模式匹配空字符串dp[0][0]=True#初始化dp[0][j],非空模式匹配范围内j的空字符串(1,p_length+1):ifp[j-1]!="*":breakdp[0][j]=Trueforiinrange(1,s_length+1):forjinrange(1,p_length+1):#如果p[j-1]==s[i-1]或p[j-1]=="?":dp[i][j]=dp[i-1][j-1]elifp[j-1]=="*":dp[i][j]=dp[i-1][j]或dp[i][j-1]returndp[s_length][p_length]实现文章原文结果，欢迎关注和点赞。微信公众号《书所集录》同步更新，也欢迎大家关注。
