欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

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

程序员文章站 2022-05-07 18:17:39
1. 题目给定一个字符串 (s) 和一个字符模式 § ,实现一个支持 ‘?’ 和 ‘*’ 的通配符匹配。‘?’ 可以匹配任何单个字符。‘*’ 可以匹配任意字符串(包括空字符串)。两个字符串完全匹配才算匹配成功。说明:s 可能为空,且只包含从 a-z 的小写字母。p 可能为空,且只包含从 a-z 的小写字母,以及字符 ? 和 *。来源:力扣(LeetCode) 链接:https://leetcode-cn.com/problems/wildcard-matching著作权归领扣网络所有。...

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]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(n2)O(n^2);
空间复杂度:O(n2)O(n^2).

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