44.通配符匹配

链接：44.通配符匹配
难度：Hard
标签：贪心、递归、字符串、动态规划
简介：给定一个字符串 (s) 和一个字符模式 (p) ，实现一个支持 '?' 和 '*' 的通配符匹配。

题解 1 - typescript

• 编辑时间：2020-07-05
• 执行用时：172ms
• 内存消耗：49.9MB
• 编程语言：typescript
• 解法介绍：如果是?或者字母，则匹配前一个，如果是*则判断前一个是否能匹配。

function isMatch(s: string, p: string): boolean {
  const sLen = s.length;
  const pLen = p.length;
  const dp = new Array(sLen + 1).fill(0).map(_ => new Array(pLen + 1).fill(false));
  dp[0][0] = true;
  for (let i = 1; i <= pLen; i++) {
    dp[0][i] = p[i - 1] === '*' && dp[0][i - 1];
  }
  for (let i = 1; i <= sLen; i++) {
    for (let j = 1; j <= pLen; j++) {
      const cP = p[j - 1];
      if (cP === '?' || s[i - 1] === cP) {
        dp[i][j] = dp[i - 1][j - 1];
      } else if (cP === '*' && (dp[i - 1][j] || dp[i][j - 1])) {
        dp[i][j] = true;
      }
    }
  }
  return dp[sLen][pLen];
}