样例 示例 1 :"aa" "a" false "a" 无法匹配 "aa" 整个字符串。2 :"aa" "*" true '*' 可以匹配任意字符串。3 :"cb" "?a" false '?' 可以匹配 'c' , 但第二个 'a' 无法匹配 'b' 。4 :"adceb" "*a*b" true '*' 可以匹配空字符串, 第二个 '*' 可以匹配字符串 "dce" .5 :"acdcb" "a*c?b" false
解题 https://www.cnblogs.com/techflow/p/12590923.html 题意很简单，给定两个字符串s和p，其中s是母串，p是模式串 。简单解释一下这两个概念，这两个概念一般出现在字符串匹配的问题当中。有些同学可能不太理解，我们打个不恰当的比方，我们可以把母串想象成锁，把模式串想象成钥匙。一些万能钥匙可以打开多把锁，也就是说钥匙是可以变化的，锁是固定的。我们要判断的就是模式串能不能匹配上母串，也就是钥匙能不能打开锁。 在模式串p当中可能出现两种特殊字符，一种是?，它表示匹配任何单一字符 。还有一种是*，它表示匹配任何一串字符 ，包括空字符串。所以这个*看起来非常强大，一个可以任意匹配。但是这题当中有一个限制，s和p必须要是完全匹配，不能是部分匹配。也就是说p当中的所有字符都要用上，举个例子，s串是aab，p串是*c。虽然*就足够匹配s串的所有内容，但是由于之后跟了一个c没有用上，所以不能算是合法匹配。 为了简化说明，我们用si表示s串的第i个字符，pi表示p串的第i个字符。 搜索 我们还是先从简单的方法构思，最先思考暴力的解法，很容易发现在这道题当中没有办法简单粗暴地暴力计算。原因也很简单，因为当出现*这个符号的时候，我们不知道它究竟应该匹配多长的字符串 。可以是0，也可以是长度任意一只匹配到结尾。 为了解决这个问题，最好的办法就是都试一试，枚举一下*这个符号应该匹配的长度。但是由于*的数量可能不止一个，如果出现多个的话，由于前后会互相影响，并且前后之间存在顺序，也就是说*这个符号如何匹配的决策不是一起做的，而是有先后的。就和八皇后当中的皇后不是一起摆放的，而是有先后顺序的，如果我们把*看成是皇后，其实这已经是比较明显的搜索问题 了。 如果想通了，把这题当成是搜索问题来解决的话，其实并不算困难，其实就是简单的枚举。 我们搜索s和p串匹配的位置，我们用si表示s串当前需要匹配的字符，pi表示p串当前需要匹配的字符。如果pi位置的字符不是*，那么情况比较有限，我们只需要判断上下界以及是否匹配即可。如果pi的位置是*，那么情况会复杂一些，因为*的出现意味着三种决策。 第一种决策是不使用*来匹配当前位置的si ，在这种情况下意味着我们抛弃这个* ，但是si还是没有找到匹配的对象，所以si不能移动，从这点出发，我们可以得到下一个转移到的位置是si，pi+1。即p当中的指针移动了一位，但是s中的指针保持不动，等待继续匹配。 第二种决策是只匹配当前的si ，不再匹配si之后的内容。在这种情况下，我们只需要把*当成是一个正常的字符处理就好了，那么我们应该转移到的位置是si+1，pi+1。也就是说s和p当中的指针各自移动了一位。 第三种决策是*不止匹配当前的si，并且还会继续往下匹配 ，在这种情况下我们需要保持pi的位置不动，只移动si，也就是说我们会转移到si+1和pi。 但是我们仔细分析一下，会发现其实这三种情况是可以合并 的。在第二种情况中，我们只匹配当前位置，其实这等价于我们在当前位置执行第三种策略，在转移之后的位置执行策略1。 举个例子：比如s串是abc，p串是a*c。我们在匹配第二个字符的时候，执行策略3，于是跳转到2, 1。也就是si是c，pi仍然是*，这个时候我们再执行策略1，则会跳转到2，2，和我们在一开始的时候执行策略2是一致的。这样在*出现很多的时候可以减少决策过程，起到加速的作用。 最后，由于这是一道搜索答案存不存在的问题，并不需要我们找到所有的解 。在这种情况下，使用bfs会比dfs效率更高，但遗憾的是这两种方法我都试过了，都无法通过，因为会超时。可能这是Python的原因（解释型语言执行效率低 ），因为我用C++是可以过的。 虽然过不了，但是思路是对的，不介意的话可以看下代码： class Solution :def isMatch (self, s: str, p: str) -> bool:len (s), len (p)if 1 and 0 ] == '*' return True import queue0 , 0 ))while not pi = que.get()if and pi == m:return True # 如果s串已经匹配完了，p串还没结束 # 需要特判一下p串当中是否是* # 如果p串的末尾都是*，那么也是可以匹配的 if if pi ] == '*' pi + 1 ))continue continue elif pi >= m:continue # 如果没有出现*，那么我们判断能否匹配 elif p[pi ] == '?' or pi ] == s[si]:1 , pi + 1 ))continue # 否则的话分两种情况往下 elif p[pi ] == '*' pi + 1 ))1 , pi ))return False 动态规划 虽然上面的方法无法通过，但其实已经给了我们很多启发了，如果我们把上面提到的si和pi看成是状态 的话，虽然我们是用bfs实现的，但本质上已经是动态规划的思想了。 在一些动态规划的问题当中，我们也是通过队列来维护状态的。我们会将合法的状态全部存储在队列当中，当我们通过状态和决策转移到新的合法状态的时候，我们继续插入队列。所以从这个角度来说动态规划和搜索问题本质是类似的，或者更准确一点说动态规划只是一种思想，它实现的载体可以多种多样 ，既可以是使用数组递推，也可以是使用数据结构维护状态。这一点非常重要，也是我们动态规划进阶的基础。 如果我们把刚才搜索的思路看成是动态规划的话，会发现这是一个顺推 的动态规划。简单介绍一下，动态规划的状态和转移虽然每题当中都不尽相同，但是整体的思路只有两种。一种叫做顺推，一种是逆推 。 在顺推思路当中，我们记录所有合法的状态，然后从合法的状态出发，通过决策进行转移 ，将转移得到的状态记录下来留待后续继续转移。如果我们把这些状态串联起来的话，会发现我们是顺着一个逻辑上的顺序执行的，所以称为顺推。逆推则恰恰相反，我们遍历未知的状态，通过状态之间的转移关系，探索它的源头 ，从而确定当前未知状态的结果。也就是说一个是从已知到未知，另一个是先获得未知再探索它已知的来源。 为什么在这题当中顺推不行呢？因为当*出现的时候，我们继续往下推进的状态当中仍然有*。比如当我们决定使用*来匹配si的时候，我们会转移到si+1，pi状态。在后序的状态当中同样包含了*，又会面临更多的状态。这些状态中间很多会出现重叠 ，并且这些重叠的状态当中有很多是剪枝也无法解决的，比如p串当中一连串的*。这个时候我们就可以换换角度思考一下逆推了。 常规套路，我们用dp[i][j]记录s[:i+1]和p[:j+1]匹配的状态，那么这个dp[i][j]可能是哪些状态转移过来的呢？其实非常有限，如果si和pi能够匹配，那么它可以从dp[i-1][j-1]转移过来。如果不匹配，我们需要判断一下pi是否是*。如果是的话，则有两种情况，一种是*匹配空，把si交给pi-1，所以可以从dp[i][j-1]转移得到。另一种是匹配si，由于*可以匹配的数量不止一个，所以这时候可以从dp[i-1][j]转移得到。由于每个i，j的状态来源非常有限，只有有限的几种 ，所以我们完全可以枚举所有的i，j进行倒推，这样的复杂度就是O(nm)，是完全可控的。 把上面这段话梳理清楚的话，这就是一个非常明显的动态规划问题了。 class Solution :def isMatch (self, s: str, p: str) -> bool:if m == 1 and p[0 '*' : return True s = ' ' + s p = ' ' + p # 注意下标，第一个range里的是列数，第二个range里的是行数 # 申请一个dp[n][m]的数组 dp = [[ False for _ in range(m+ 2 )] for _ in range(n+ 2 )] dp[ 0 ][ 0 ] = True # i从0开始，因为p的开头出现*可以匹配空串 for i in range(0 , n+1 ):for j in range(1 , m+1 ):# si和pj匹配 if s[i ] == p[j ] or p[j ] == '?' :i ][j ] = dp[i -1 j -1 if i > 0 else False continue # pj出现*，这时候判断上游能否有合法的转移 if p[j] == '* 'i ][j ] = (dp[i -1 j ] if i > 0 else False ) | dp[i ][j -1 return dp[n ][m ]这段代码虽然短，但是其中的细节不少，包括下标以及边界等条件 。所以建议大家理解思路之后上手写过再来对照代码进行思考，相信会有更多收获。因为很多细节可能是需要看到了错误的case进行思考之后才会明白，这也是LeetCode当中一个比较好的点，可以看到测试数据，可以知道自己错在哪里。 好了，今天的文章就到这里，如果觉得有所收获，请顺手点个在看 或者转发吧，你们的支持是我最大的动力。 
