我要评论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. 解法
常见两个字符串的比较，比如找最长公共子串等题目，这个类型一般通过定义二维数组, 含义为 字符串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)]
时间复杂度：;
空间复杂度：.
本文地址：https://blog.csdn.net/rosefun96/article/details/107141513
您可能感兴趣的文章:
如您对本文有疑问或者有任何想说的，请 点击进行留言回复，万千网友为您解惑！
网友评论