LeetCode44. 通配符匹配(python,动态规划) 通用解法

1. 题目

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

‘?’ 可以匹配任何单个字符。
‘*’ 可以匹配任意字符串（包括空字符串）。
两个字符串完全匹配才算匹配成功。

说明:

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

来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/wildcard-matching
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

示例 1:

输入:

s = "aa"
p = "a"

输出: false
解释: “a” 无法匹配 “aa” 整个字符串。

2. 解法

常见两个字符串的比较，比如找最长公共子串等题目，这个类型一般通过定义二维数组$dp[i][j]$, 含义为 字符串1 s[:(i-1)] 和字符串p[:(j-1)] 是否能够完全匹配（这样dp[0][0]可以覆盖特殊情况s,p 其中一个是空字符串的情形）。

然后考虑状态转移方程，这里，主要是 * ，? 和普通字符三种。如果是普通字符，只需要考虑 s[i] == s[j] 以及前面字符是否能完全匹配dp[i-1][j-1]. ? 也是这种情况。 如果p[j-1] == '*'， 就要考虑三种小情况， * 作为空字符串，需要判断状态dp[i][j-1]; * 作为任意单个字符，需要判断dp[i-1][j-1]; *作为一串字符，这时考虑dp[i-1][j]（这里代表 * 匹配 s 索引i-1 及它前面的元素）。

class Solution:
    def isMatch(self, s: str, p: str) -> bool:
        dp = [[False for _ in range(len(p)+1)] for _ in range(len(s)+1)]
        dp[0][0] = True
        for i in range(len(s)+1):
            for j in range(1,len(p)+1):
                if p[j-1] == '*':
                    if i == 0:
                        dp[i][j] = dp[i][j-1]
                    else:
                        if dp[i-1][j-1] or dp[i-1][j] or dp[i][j-1]:
                            dp[i][j] = True
                else:
                    if i == 0:
                        break
                    if s[i-1] == p[j-1] or p[j-1] == '?':
                        if dp[i-1][j-1]:
                            dp[i][j] = True
        return dp[len(s)][len(p)]

时间复杂度：$O(n^2)$;
空间复杂度：$O(n^2)$.

本文地址：https://blog.csdn.net/rosefun96/article/details/107141513