【小白用python刷Leetcode】44.通配符匹配

44.通配符匹配

题目描述

给定一个字符串 (s) 和一个字符模式 (p) ，实现一个支持 '?' 和 '*' 的通配符匹配。

• '?' 可以匹配任何单个字符。
• '*' 可以匹配任意字符串（包括空字符串）。

两个字符串完全匹配才算匹配成功。

说明:

• s 可能为空，且只包含从 a-z 的小写字母。
• p 可能为空，且只包含从 a-z 的小写字母，以及字符 ? 和 *。

示例：

输入:
s = "aa"
p = "a"
输出: false
解释: "a" 无法匹配 "aa" 整个字符串。

输入:
s = "aa"
p = "*"
输出: true
解释: '*' 可以匹配任意字符串。

输入:
s = "cb"
p = "?a"
输出: false
解释: '?' 可以匹配 'c', 但第二个 'a' 无法匹配 'b'。

输入:
s = "adceb"
p = "*a*b"
输出: true
解释: 第一个 '*' 可以匹配空字符串, 第二个 '*' 可以匹配字符串 "dce".

输入:
s = "acdcb"
p = "a*c?b"
输出: false

 

官方思路

哈哈，是的，这道题又没做出来，所以依然只有官方思路（还有点高兴和骄傲是怎么回事，而且在秋招的笔试中似乎还见过这道，当时就没做出来。。。）。一天写两道题可太酸爽了，谁让咱昨天没写完呢，看出咱菜了吧。

这题我主要研究了动态规划的思路，感觉更普适一些。研究了一下发现其实和最长子序列（or子串）的那种动态规划有点像，自以为对那题已经熟稔的我，对上这道题居然没什么思路，实在不应该啊。言归正传，大致思路就是创建一个二维列表dp来存储以s[j]和p[i]作为结尾的子串是否匹配。dp的size为m*n，m = len(p)+1，n = len(s)+1，之所以都+1的原因是要给初条件预留空间。这里必须要注意一下，dp[i][j]在两个字符串中所对应的位置为s[j-1]和p[i-1]，因为我们把首行首列作为初条件预留，所以i和j的遍历都是从1开始，而字符串的第一位却是从0开始，所以-1后才是在字符串中的相应位置。在dp[i][j]置0，表示以s[j-1]和p[i-1]作为结尾的子串不匹配；反之，置1则为匹配。初始化dp的时候，先将其全部置0，这样后来只需考虑匹配的情况，并将dp的相应位置置1即可。

对于动态规划来说，首先要考虑的就是状态转移方程。之前我们提到，我们只需关注匹配的情况，即dp[i][j]置1的情况。这道题的状态转移方程可以分为三种情况：1. 两个字符串的当前位上字符是相同的，即s[i-1] = p[i-1]，则以当前这两个字符作为结尾的子串是否匹配取决于前一个状态量，即dp[i][j] = dp[i-1][j-1]；2. p串当前字符为'?'，根据题目描述，这个'?'必须要占一位，但是它可以为任意字符。那这种情况其实和前一种情况可以合并，因为不论s[j-1]是什么，s[i-1] = p[i-1]实际都成立，那么与前一种情况一样，dp[i][j] = dp[i-1][j-1]；3. p串当前字符为'*'，根据题目描述，这个'*'可以为任意长度、任意字符串，也就是说，这个'*'也可以为空串，不占位。在这种情况下，又可以分出两种子情况，其一是'*'确实就是一空串，不占位，那么相当于p在这里少了一位，要判断的是s[j-1]与p[i-2]的匹配关系，即dp[i][j] = dp[i-1][j]；其二是'*'不作为空串，作为任意字符串占位，那么s[j-1]是啥根本不重要，因为不管是啥p的'*'都能适配，所以影响当前dp[i][j]的实际上是s[j-2]与p[i-1]的匹配情况，即dp[i][j] = dp[i][j-1]。为啥是p[i-1]而不是p[i-2]呢，因为'*'占位了呀，最起码要占一位啊。而以上两种子情况，是逻辑上或的关系（or），因为'*'可以占位也可以不占位，有一个满足即可，那么归一下情况3的状态转移方程可以写为dp[i][j] = dp[i-1][j] or dp[i][j-1]，任一为1，则dp[i][j]置1。

看完状态转移方程，我们来看初条件。本题初条件有三：dp[0][0]、dp[i][0]和dp[0][j]。首先，dp[0][0]表示s和p都为空，其实是有效匹配，所以dp[0][0]置1。其次，dp[i][0]表示只有p而s为空，此时如果p全为'*'，dp[i][0]才置1，否则置0（但是由于初始化全置0的原因，代码就不体现了）。最后，dp[0][j]表示p为空而s不为空，明显这种情况不可能实现，所以dp[0][j]全置0，同样由于初始化，代码也不体现。

最后，dp的右下角dp[-1][-1]就是我们一路状态转移过来要的结果。

题解代码：

def isMatch(self, s: str, p: str) -> bool:
        m = len(p)+1
        n = len(s)+1
        dp = [[0 for _ in range(n)] for _ in range(m)]
        # 初条件设定
        dp[0][0] = 1
        for i in range(1,m):
            if p[i-1] == '*':  # 为'*'才成立
                dp[i][0] = 1
            else:
                break
        # 遍历
        for i in range(1,m):
            for j in range(1,n):  # 由于初条件占行，所以都从1开始遍历
                if p[i-1] == s[j-1] or p[i-1] =='?':  # 要注意下标退一位
                    dp[i][j] = dp[i-1][j-1]
                elif p[i-1] == '*':
                    if dp[i-1][j] or dp[i][j-1]:  # 或的逻辑关系实现
                        dp[i][j] = 1
        return dp[-1][-1] == 1  #最后要返回Ture or False而不是0或1

官方思路果然香，效率十分优秀，时间和空间复杂度都是 O(mn)。其实我觉得，我们只需要记录并一直迭代维护dp[i-1][j-1]、dp[i][j-1]和dp[i-1][j-1]这三个值就好，是不是可以省省空间？小白的想法，欢迎指正。

运行结果：

我觉得这道题，官方题解其实讲的比我清楚明白，所以我决定奉上链接：官方题解方法一。如果您有啥不明白的地方，我也没说透（我理解动态规划的确是有些吃力，更别说要写出来），您可以再看看参考参考。不过也许万一有和我一样的初学者更容易和我产生共鸣，看我写的觉得更明白，那我的初心的一部分也就达到了（另一部分是给自己做笔记看），谢谢！

以上就是我，一个正儿八经的小白（大神们通过看代码应该也感觉出来了），对这道题的理解，欢迎诸位指正讨论，感谢阅读。

原题链接：

https://leetcode-cn.com/problems/wildcard-matching/submissions/

本文地址：https://blog.csdn.net/qq_30388425/article/details/107147728