实现支持通配符的字符串匹配算法

题目

实现支持通配符的字符串匹配算法

信息

• 类型：问答
• 难度：⭐⭐⭐

考点

动态规划, 字符串匹配, 通配符处理

快速回答

该问题可通过动态规划解决，核心思路如下：

• 定义二维DP数组，dp[i][j]表示模式串前j字符是否匹配文本串前i字符
• 处理三种通配符：
  • 普通字符：需精确匹配
  • '?'：匹配任意单个字符
  • '*'：匹配零个或多个任意字符
• 状态转移方程：
  • 若p[j-1]=='*'：dp[i][j] = dp[i][j-1]（匹配0次） || dp[i-1][j]（匹配多次）
  • 否则：dp[i][j] = dp[i-1][j-1] && (s[i-1]==p[j-1] || p[j-1]=='?')
• 时间复杂度O(mn)，空间复杂度可优化至O(n)

问题描述

实现一个支持通配符的字符串匹配函数，其中：

• '?' 匹配任意单个字符
• '*' 匹配零个或多个任意字符
• 函数签名：bool isMatch(string s, string p)
• 示例：
  • isMatch("adceb", "*a*b") → true
  • isMatch("acdcb", "a*c?b") → false

核心算法：动态规划

DP数组定义

dp[i][j] = true 表示文本串s的前i个字符与模式串p的前j个字符匹配

状态转移方程

1. 初始化：
   dp[0][0] = true  // 空模式匹配空文本
   dp[0][j] = dp[0][j-1] && p[j-1]=='*'  // 模式前缀全为*才匹配空文本

2. 状态转移：
   if p[j-1] == '*':
      dp[i][j] = dp[i][j-1]   // 匹配0个字符
               || dp[i-1][j]  // 匹配当前字符并继续用*匹配
   else:
      dp[i][j] = dp[i-1][j-1] && (s[i-1]==p[j-1] || p[j-1]=='?')

代码实现

bool isMatch(string s, string p) {
    int m = s.size(), n = p.size();
    vector<vector<bool>> dp(m+1, vector<bool>(n+1, false));

    // 初始化
    dp[0][0] = true;
    for (int j = 1; j <= n; j++) {
        dp[0][j] = dp[0][j-1] && p[j-1] == '*';
    }

    // DP计算
    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= n; j++) {
            if (p[j-1] == '*') {
                dp[i][j] = dp[i][j-1] || dp[i-1][j];
            } else {
                dp[i][j] = dp[i-1][j-1] && (s[i-1] == p[j-1] || p[j-1] == '?');
            }
        }
    }
    return dp[m][n];
}

优化方案

• 空间优化：使用滚动数组将空间复杂度降至O(n)

  vector<bool> dp(n+1, false);
  // 初始化dp[0..n]
  for (int j = 1; j <= n; j++) dp[j] = dp[j-1] && p[j-1]=='*';
  
  for (int i = 1; i <= m; i++) {
      vector<bool> newDp(n+1, false);
      for (int j = 1; j <= n; j++) {
          if (p[j-1]=='*') newDp[j] = newDp[j-1] || dp[j];
          else newDp[j] = dp[j-1] && (s[i-1]==p[j-1] || p[j-1]=='?');
      }
      dp = newDp;
  }

• 剪枝优化：记录最后一个'*'位置，避免无效计算

常见错误

• 未正确处理连续'*'：多个'*'等价于一个'*'
• 边界条件错误：空字符串与全'*'模式的匹配
• 状态转移遗漏：'*'匹配时忽略dp[i-1][j]分支
• 空间优化时未保存上一行完整状态

扩展知识

• NFA/DFA解法：将模式转换为非确定有限自动机
• 贪心+回溯：记录'*'位置和匹配点，失败时回溯（最坏O(mn)）
• 不同通配符语义：正则表达式中的'+'、'{m,n}'等扩展
• 实际应用：文件路径匹配（如.gitignore）、搜索引擎关键词匹配