type
status
date
summary
tags
category
icon
password
featured
freq
difficulty
给你一个输入字符串 (
s) 和一个字符模式 (p) ,请你实现一个支持 '?' 和 '*' 匹配规则的通配符匹配:'?'可以匹配任何单个字符。
'*'可以匹配任意字符序列(包括空字符序列)。
判定匹配成功的充要条件是:字符模式必须能够 完全匹配 输入字符串(而不是部分匹配)。
示例 1:
示例 2:
示例 3:
提示:
0 <= s.length, p.length <= 2000
s仅由小写英文字母组成
p仅由小写英文字母、'?'或'*'组成
解法一:2d 动态规划
状态
dp[i][j]:s[:i] 与 p[:j] 是否匹配(i、j 都是长度,空串用 0)。初始化
dp[0][0] = True
dp[0][j]:仅当p[:j]全是 时为 True( 可匹配空串)。
转移
- 普通字符或
?:
dp[i][j] = dp[i-1][j-1] and (p[j-1] == s[i-1] or p[j-1] == '?')*:- 视作空串:
dp[i][j-1] - 吞 1 个字符(继续吞也被归纳进来):
dp[i-1][j]→dp[i][j] = dp[i][j-1] or dp[i-1][j]
复杂度:
时间:
O(mn)空间:
O(mn)。解法二:1d 动态规划
- 只使用长度为
n+1的一维数组dp和辅助数组dp2实现空间优化。
- 每次迭代时,根据
dp更新dp2,代表当前行i。
- 通过
if not any(dp): return False实现提前结束,避免无效计算。
复杂度:时间
O(mn);空间 O(n)。解法三:双指针 + 回溯 (最优)
在扫描字符串和模式时,如果遇到不匹配的字符,尝试利用之前遇到的
*,通过回退模式指针到*的位置+1,并让*多匹配一个字符(即多“吞”一个字符),去重新尝试匹配剩余字符串。通过记录最近出现的的位置和该位置匹配字符串的起点,保证了回溯时能够向后“扩展”
*的吞噬范围,从而保证了所有可能从宽匹配到窄的路径都能被探索。复杂度:
- 时间:O(m+n),两个指针共向前移动最多各一次。
- 空间:O(1) 。(最坏回退很多)
- 作者:Fan Luo
- 链接:https://fanluo.me/article/leetcode-44-通配符匹配
- 声明:本文采用 CC BY-NC-SA 4.0 许可协议,转载请注明出处。
上一篇
[Leetcode 42] 接雨水
下一篇
[Leetcode 46] 全排列