44.通配符匹配

通配符匹配

给你一个输入字符串 (s) 和一个字符模式 (p) ，请你实现一个支持 ‘?’ 和 ‘*‘ 匹配规则的通配符匹配：

• ‘?’ 可以匹配任何单个字符。
• ‘*‘ 可以匹配任意字符序列（包括空字符序列）。

判定匹配成功的充要条件是：字符模式必须能够 完全匹配 输入字符串（而不是部分匹配）。

示例 1：

输入：s = “aa”, p = “a”
输出：false

示例 2：

输入：s = “aa”, p = “*“
输出：true

示例 3：

输入：s = “cb”, p = “?a”
输出：false

提示：

• 0 <= s.length, p.length <= 2000
• s 仅由小写英文字母组成
• p 仅由小写英文字母、’?’ 或 ‘*‘ 组成

解析

动态规划，dp[i][j] 表示 s 的前 i 个字符和 p 的前 j 个字符是否匹配。

/**
 * @param {string} s
 * @param {string} p
 * @return {boolean}
 */
var isMatch = function (s, p) {
  const m = s.length;
  const n = p.length;
  const dp = Array.from({ length: m + 1 }, () => Array(n + 1).fill(false));
  dp[0][0] = true;

  // 初始化：p 的前缀全为 * 时可以匹配空串
  for (let j = 1; j <= n; j++) {
    if (p[j - 1] === "*") {
      dp[0][j] = dp[0][j - 1];
    }
  }

  for (let i = 1; i <= m; i++) {
    for (let j = 1; j <= n; j++) {
      if (p[j - 1] === "*") {
        // * 匹配空序列 或 匹配一个字符后继续
        dp[i][j] = dp[i][j - 1] || dp[i - 1][j];
      } else if (p[j - 1] === "?" || p[j - 1] === s[i - 1]) {
        dp[i][j] = dp[i - 1][j - 1];
      }
    }
  }
  return dp[m][n];
};

与第 10 题类似的 DP 思路，区别在于这里的 * 可以独立匹配任意序列，不需要与前面字符配合。时间复杂度 O(mn)。