线性动态规划：通配符匹配（Wildcard Matching）
字数 1572 2025-10-31 08:19:17

线性动态规划：通配符匹配（Wildcard Matching）

题目描述
给定一个字符串 s 和一个包含通配符的模式串 p，实现一个函数来判断 s 是否匹配 p。模式 p 可能包含以下两种通配符：

  • '?' 可以匹配任意单个字符。
  • '*' 可以匹配任意字符序列（包括空序列）。
    要求完整匹配整个字符串 s，而非部分匹配。

示例

  • 输入：s = "adceb", p = "ab"
    输出：true（解释：'' 匹配空序列，"a" 匹配 'a'，'' 匹配 "dce"，"b" 匹配 'b'）
  • 输入：s = "acdcb", p = "a*c?b"
    输出：false（'?' 无法匹配 'c' 后的字符 'b'，但模式要求 '?' 后是 'b'，实际 'b' 已不存在）

解题过程

步骤1：定义状态
使用动态规划表 dp[i][j]，表示字符串 s 的前 i 个字符与模式 p 的前 j 个字符是否匹配。

  • i 和 j 分别表示 s 和 p 的字符索引（从1开始计数）。
  • 初始状态 dp[0][0] = true，表示两个空字符串匹配。

步骤2：处理空字符串的匹配情况

  • 若 s 为空（i=0），则只有当 p 的前 j 个字符全部为 '*' 时才可能匹配，因为 '*' 可以匹配空序列。
    初始化： 
    for j in range(1, len(p)+1):
    if p[j-1] == '*':
        dp[0][j] = dp[0][j-1]  # 连续 '*' 保持匹配空串
    else:
        break  # 遇到非 '*' 字符则无法匹配空串

步骤3：状态转移方程
遍历 i 从 1 到 len(s)，j 从 1 到 len(p)：

  1. Case 1: 字符匹配或 p[j-1] 为 '?'
    • 当前字符匹配（s[i-1] == p[j-1]）或 p[j-1] == '?' 时，dp[i][j] 取决于前一个状态：
      dp[i][j] = dp[i-1][j-1]
  2. Case 2: p[j-1] 为 '*'
    • '*' 可以匹配空序列（即忽略 '*'）：dp[i][j] = dp[i][j-1]
    • '*' 可以匹配多个字符（即 s 的当前字符被 '*' 吞噬）：dp[i][j] = dp[i-1][j]
    • 综合两种情况：dp[i][j] = dp[i][j-1] or dp[i-1][j]

步骤4：示例推导（s="adceb", p="ab"）

  1. 初始化 dp[0][0] = true，dp[0][1] = true（因为 p[0]='*'）。
  2. 逐步填充表格（详见下表，√ 表示 true）：
    "" * a * b
    "" √ √
    a √ √ √
    d √ √
    c √ √
    e √ √
    b √ √ √
  3. 最终 dp[5][4] = true，匹配成功。

步骤5：优化空间复杂度
由于 dp[i][j] 仅依赖当前行和上一行，可将二维数组优化为两个一维数组，空间复杂度从 O(mn) 降为 O(n)。

关键点

  • 通配符 '*' 的状态转移需同时考虑匹配空序列或连续字符。
  • 初始化时需正确处理模式开头连续 '*' 匹配空字符串的情况。
  • 实际编码中需注意字符串索引从0开始的细节。

通过以上步骤，可高效解决通配符匹配问题，算法时间复杂度为 O(mn)，空间复杂度可优化至 O(min(m, n))。

线性动态规划：通配符匹配（Wildcard Matching） 题目描述 给定一个字符串 s 和一个包含通配符的模式串 p ，实现一个函数来判断 s 是否匹配 p 。模式 p 可能包含以下两种通配符： '?' 可以匹配任意单个字符。 '*' 可以匹配任意字符序列（包括空序列）。 要求完整匹配整个字符串 s ，而非部分匹配。 示例 输入：s = "adceb", p = " a b" 输出：true（解释：' ' 匹配空序列，"a" 匹配 'a'，' ' 匹配 "dce"，"b" 匹配 'b'） 输入：s = "acdcb", p = "a* c?b" 输出：false（'?' 无法匹配 'c' 后的字符 'b'，但模式要求 '?' 后是 'b'，实际 'b' 已不存在） 解题过程 步骤1：定义状态 使用动态规划表 dp[i][j] ，表示字符串 s 的前 i 个字符与模式 p 的前 j 个字符是否匹配。 i 和 j 分别表示 s 和 p 的字符索引（从1开始计数）。 初始状态 dp[0][0] = true ，表示两个空字符串匹配。 步骤2：处理空字符串的匹配情况 若 s 为空（i=0），则只有当 p 的前 j 个字符全部为 '*' 时才可能匹配，因为 '*' 可以匹配空序列。 初始化： 步骤3：状态转移方程 遍历 i 从 1 到 len(s) ， j 从 1 到 len(p) ： Case 1: 字符匹配或 p[j-1] 为 '?' 当前字符匹配（ s[i-1] == p[j-1] ）或 p[j-1] == '?' 时， dp[i][j] 取决于前一个状态： dp[i][j] = dp[i-1][j-1] Case 2: p[j-1] 为 '*' '*' 可以匹配空序列（即忽略 '*' ）： dp[i][j] = dp[i][j-1] '*' 可以匹配多个字符（即 s 的当前字符被 '*' 吞噬）： dp[i][j] = dp[i-1][j] 综合两种情况： dp[i][j] = dp[i][j-1] or dp[i-1][j] 步骤4：示例推导（s="adceb", p=" a b"） 初始化 dp[0][0] = true ， dp[0][1] = true （因为 p[ 0]='* '）。 逐步填充表格（详见下表，√ 表示 true）： | | "" | * | a | * | b | |-----|----|----|----|----|----| | "" | √ | √ | | | | | a | | √ | √ | √ | | | d | | √ | | √ | | | c | | √ | | √ | | | e | | √ | | √ | | | b | | √ | | √ | √ | 最终 dp[5][4] = true ，匹配成功。 步骤5：优化空间复杂度 由于 dp[i][j] 仅依赖当前行和上一行，可将二维数组优化为两个一维数组，空间复杂度从 O(mn) 降为 O(n)。 关键点 通配符 '*' 的状态转移需同时考虑匹配空序列或连续字符。 初始化时需正确处理模式开头连续 '*' 匹配空字符串的情况。 实际编码中需注意字符串索引从0开始的细节。 通过以上步骤，可高效解决通配符匹配问题，算法时间复杂度为 O(mn)，空间复杂度可优化至 O(min(m, n))。