44-通配符匹配.md

44-通配符匹配

原题

给定一个字符串 (s) 和一个字符模式 (p) ，实现一个支持 '?' 和 '*' 的通配符匹配。 '?' 可以匹配任何单个字符。 '*' 可以匹配任意（一个或多个）字符串（包括空字符串）。

两个字符串完全匹配才算匹配成功。

说明:

s  可能为空，且只包含从  a-z  的小写字母。 p  可能为空，且只包含从  a-z  的小写字母，以及字符  ?  和  *。

题解参考

const isMatch = function (s, p) {
  const sLen = s.length;
  const pLen = p.length;

  const dp = Array.from({ length: sLen + 1 }, () => Array.from({ length: pLen + 1 }).fill(false));

  dp[0][0] = true;
  for (let j = 1; j <= pLen; j++) {
    // 这里的条件没太懂啊
    dp[0][j] = p[j - 1] === '*' && dp[0][j - 1];
  }

  // 迭代
  for (let i = 1; i <= sLen; i++) {
    for (let j = 1; j <= pLen; j++) {
      if (p[j - 1] === '?' || s[i - 1] === p[j - 1]) {
        dp[i][j] = dp[i - 1][j - 1];
      } else if (
        p[j - 1] === '*' &&
        // 这个条件没太懂啊
        (dp[i - 1][j] || dp[i][j - 1])
      ) {
        dp[i][j] = true;
      }
    }
  }

  return dp[sLen][pLen];
};

let result = isMatch('cb', '?a');
console.log(result);

上面的太复杂了 直接两个 for 渲染加一个标记符就可以了

1. s 是全字母，所以一次渲染
2. p 中有 ? _，所以有 ？就直接 continue，如果有 _ 就标记一下，记录 tag = p[j+1] 也就是*的下一位是什么
3. s 会继续循环，所以看后续有没有匹配到 tag 的，没有就 return false, 有就匹配了，然后 tag 重置为空，然后继续走正常的 for 渲染