通配符与正则匹配

两个匹配问题的模式字符有什么差别？

问题	单字符通配	量词	其它
通配符匹配 (44)	? 匹配任意一个字符	* 匹配任意长度序列 (含空)	小写字母
正则匹配 (10)	. 匹配任意一个字符	* 修饰前一个字符, 表示 0 到多次	小写字母

• 共同状态: dp[i][j] 表示 s 前 i 个字符与 p 前 j 个字符是否匹配;
• 共同初值: dp[0][0] = true, 其余为 false;
• 共同答案: dp[m][n];

通配符匹配的转移方程如何写？

• 单字符匹配: s[i-1] === p[j-1] 或 p[j-1] === "?", 则 dp[i][j] = dp[i-1][j-1];
• * 匹配: 可以吃掉 0 个或多个字符;
  • 吃掉 0 个: dp[i][j-1];
  • 吃掉至少 1 个: dp[i-1][j] (把 s 的末位交给 * 继续持有);
  • 合并: dp[i][j] = dp[i-1][j] || dp[i][j-1];
• 初值补充: p 以若干个 * 开头时可匹配空串, 令 dp[0][j] = true 直到遇到非 *;

const isMatchWildcard = (s, p) => {
  const m = s.length;
  const n = p.length;
  const dp = Array.from({ length: m + 1 }, () => new Array(n + 1).fill(false));
  dp[0][0] = true;
  for (let j = 1; j <= n; j++) {
    if (p[j - 1] !== "*") break;
    dp[0][j] = true;
  }
  for (let i = 1; i <= m; i++) {
    for (let j = 1; j <= n; j++) {
      if (s[i - 1] === p[j - 1] || p[j - 1] === "?") dp[i][j] = dp[i - 1][j - 1];
      else if (p[j - 1] === "*") dp[i][j] = dp[i - 1][j] || dp[i][j - 1];
    }
  }
  return dp[m][n];
};

正则匹配的转移方程如何写？

• 单字符匹配: s[i-1] === p[j-1] 或 p[j-1] === ".", 则 dp[i][j] = dp[i-1][j-1];
• * 修饰前一个字符 p[j-2] 时:
  • 无法匹配: s[i-1] !== p[j-2] 且 p[j-2] !== ".", 只能让 x* 整体匹配 0 次, dp[i][j] = dp[i][j-2];
  • 可以匹配: 取 0 次或 1 次以上合并, dp[i][j] = dp[i][j-2] || dp[i-1][j];
    • dp[i][j-2]: x* 匹配 0 次;
    • dp[i-1][j]: s 末位交给 x* 吃掉, 量词继续持有;
• 初值补充: p 形如 a*b*c* 时可匹配空串, 令 dp[0][j] = dp[0][j-2] (当 p[j-1] === "*");

const isMatchRegex = (s, p) => {
  const m = s.length;
  const n = p.length;
  const dp = Array.from({ length: m + 1 }, () => new Array(n + 1).fill(false));
  dp[0][0] = true;
  for (let j = 1; j <= n; j++) {
    if (p[j - 1] === "*") dp[0][j] = dp[0][j - 2];
  }
  for (let i = 1; i <= m; i++) {
    for (let j = 1; j <= n; j++) {
      if (s[i - 1] === p[j - 1] || p[j - 1] === ".") dp[i][j] = dp[i - 1][j - 1];
      else if (p[j - 1] === "*") {
        if (s[i - 1] !== p[j - 2] && p[j - 2] !== ".") dp[i][j] = dp[i][j - 2];
        else dp[i][j] = dp[i][j - 2] || dp[i - 1][j];
      }
    }
  }
  return dp[m][n];
};

• 复杂度: 两题均为时间 O(mn), 空间 O(mn);

两个量词的合并写法为什么成立？

• 通配符 *: dp[i-1][j] || dp[i][j-1] 已经把"吃掉当前字符"和"不吃"两层展开全部穷举;
• 正则 x*: dp[i-1][j] 自身继续调用本行同列状态, 等价于 x 匹配 1、2、3… 次的求和, 因此不必再枚举次数;