难度: Hard
s) 和一个字符模式 (p) ，请你实现一个支持 '?' 和 '*' 匹配规则的通配符匹配：'?' 可以匹配任何单个字符。'*' 可以匹配任意字符序列（包括空字符序列）。判定匹配成功的充要条件是：字符模式必须能够 完全匹配 输入字符串（而不是部分匹配）。
示例 1：
输入：s = "aa", p = "a" 输出：false 解释："a" 无法匹配 "aa" 整个字符串。
示例 2：
输入：s = "aa", p = "*" 输出：true 解释：'*' 可以匹配任意字符串。
示例 3：
输入：s = "cb", p = "?a" 输出：false 解释：'?' 可以匹配 'c', 但第二个 'a' 无法匹配 'b'。
提示：
0 <= s.length, p.length <= 2000s 仅由小写英文字母组成p 仅由小写英文字母、'?' 或 '*' 组成运行时间: 688 ms
内存: 128.8 MB
class Solution:
def isMatch(self, s: str, p: str) -> bool:
m = len(s)
n = len(p)
memo = dict()
def dp(i, j):
if j == n:
return i == m
if i == m:
while j < n:
if p[j] != '*':
return False
j += 1
return True
if (i, j) in memo:
return memo[(i, j)]
res = False
if s[i] == p[j] or p[j] == '?':
res = dp(i+1, j+1)
elif p[j] == '*':
res = dp(i+1, j) or dp(i, j+1)
memo[(i, j)] = res
return res
return dp(0, 0)
该题解使用动态规划的思路来解决通配符匹配问题。定义状态 dp(i, j) 表示字符串 s 的前 i 个字符和模式 p 的前 j 个字符是否匹配。通过分情况讨论当前字符是否匹配以及 '*' 的处理，递归地计算状态值。为了避免重复计算，使用记忆化搜索将已计算过的状态存储起来。最终的答案即为 dp(0, 0) 的结果。
时间复杂度: O(mn)
空间复杂度: O(mn)
class Solution:
def isMatch(self, s: str, p: str) -> bool:
m = len(s)
n = len(p)
memo = dict()
def dp(i, j):
# base case 1: 模式已经匹配完
if j == n:
return i == m
# base case 2: 字符串已经匹配完
if i == m:
# 检查模式剩余部分是否全为 '*'
while j < n:
if p[j] != '*':
return False
j += 1
return True
# 检查记忆化搜索结果
if (i, j) in memo:
return memo[(i, j)]
res = False
# 情况 1: 当前字符匹配成功或遇到 '?'
if s[i] == p[j] or p[j] == '?':
res = dp(i+1, j+1)
# 情况 2: 遇到 '*'
elif p[j] == '*':
res = dp(i+1, j) or dp(i, j+1)
# 存储记忆化搜索结果
memo[(i, j)] = res
return res
return dp(0, 0)
在动态规划方法中，当字符串s和模式p都为空时，dp(0, 0)应该返回True。这是因为一个空的字符串和一个空的模式是完美匹配的。该情况是递归的基本情况之一，在代码中通过检查j是否等于模式p的长度n（且i等于字符串s的长度m）来判断并返回True，表示两者都已完全匹配。
`*`可以匹配任意字符串（包括空字符串）。在动态规划中，`dp(i+1, j)`表示`*`匹配字符串s中位置i的字符后继续匹配后面的字符，而`dp(i, j+1)`表示`*`匹配空字符串，即跳过`*`，看模式p的下一个字符和字符串s当前的字符是否匹配。这样的设计使得`*`的灵活匹配得以实现，确保所有可能的情况都被考虑到。
为了防止递归调用导致栈溢出，特别是在字符串和模式长度非常大时，动态规划实现中引入了记忆化搜索。通过存储已经计算过的dp(i, j)结果，当再次计算相同的i和j时，可以直接从存储中获取结果，避免了深层次的递归调用。这种方法不仅提高了算法的效率，也减少了栈的使用，从而避免了栈溢出的风险。
记忆化搜索在动态规划中的实现通常通过使用一个哈希表（或字典）来存储已计算的dp(i, j)结果。在本题的实现中，使用了一个名为`memo`的字典来存储这些值，其中键是一个由i和j组成的元组，值是计算得到的布尔结果。每次在计算dp(i, j)之前，先检查`(i, j)`是否存在于`memo`中。如果存在，直接使用存储的结果。如果不存在，进行计算并将结果存入`memo`，以供未来的查询使用。这种方法有效地减少了重复的计算，提高了算法的效率。