[Leetcode 44] 通配符匹配

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) 。(最坏回退很多)
上一篇
[Leetcode 42] 接雨水
下一篇
[Leetcode 46] 全排列