一天一大 leet(正则表达式匹配)难度:困难 DAY-20

'.' 匹配任意单个字符
'*' 匹配零个或多个前面的那一个元素

输入:
s = "aa"
p = "a"
输出: false
解释: "a" 无法匹配 "aa" 整个字符串。

输入:
s = "aa"
p = "a*"
输出: true
解释: 因为 '*' 代表可以匹配零个或多个前面的那一个元素, 
      在这里前面的元素就是 'a'。
      因此，字符串 "aa" 可被视为 'a' 重复了一次。

输入:
s = "ab"
p = ".*"
输出: true
解释: ".*" 表示可匹配零个或多个（'*'）任意字符（'.'）。

输入:
s = "aab"
p = "c*a*b"
输出: true
解释: 因为 '*' 表示零个或多个，这里 'c' 为 0 个, 'a' 被重复一次。
      因此可以匹配字符串 "aab"。

输入:
s = "mississippi"
p = "mis*is*p*."
输出: false

// p中只包含.*及a-z
new RegExp(p).test(s);

/**
 * @param {string} s
 * @param {string} p
 * @return {boolean}
 */
var isMatch = function(s, p) {
  let m = s.length, n = p.length, f = new Array(m + 1);
  for (let v = 0; v < m + 1; v++) f[v] = new Array(n + 1);
  f[0][0] = true;
  for (var i = 0; i <= m; ++i) {
    for (var j = 1; j <= n; ++j) {
      if (p.charAt(j - 1) == '*') {
        f[i][j] = f[i][j - 2];
        if (matches(s, p, i, j - 1)) {
          f[i][j] = f[i][j] || f[i - 1][j];
        }
      }
      else {
        if (matches(s, p, i, j)) {
          f[i][j] = f[i - 1][j - 1];
        }
      }
    }
  }
  function matches(s, p, i, j) {
    if (i == 0) {
      return false;
    }
    if (p.charAt(j - 1) == '.') {
      return true;
    }
    return s.charAt(i - 1) == p.charAt(j - 1);
  }
  return Boolean(f[m][n]);
}

/**
 * @param {string} s
 * @param {string} p
 * @return {boolean}
 */
var isMatch = function(s, p) {
    if (s == null || p == null) return false
  let len1 = s.length, len2 = p.length
  let dp = new Array(len1 + 1)
  for (let i = 0; i < dp.length; i++)
    dp[i] = new Array(len2 + 1).fill(false) // 将项默认为false

  dp[0][0] = true
  for (let j = 1; j < len2 + 1; j++) {
    if (p[j - 1] == '*')
      dp[0][j] = dp[0][j - 2]
  }
  for (let i = 1; i < len1 + 1; i++) {
    for (let j = 1; j < len2 + 1; 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] || dp[i - 1][j - 2] || dp[i - 1][j]
        else
          dp[i][j] = dp[i][j - 2]
      }
    }
  }
  return dp[len1][len2] // len1长度的s串 是否匹配 len2长度的p串
};

/**
 * @param {string} s
 * @param {string} p
 * @return {boolean}
 */
  var isMatch = function (s, p) {
    if (p.length < 1) {
      return !s.length
    }
    var match = false

    if (s.length > 0 && (s[0] == p[0] || p[0] == '.')) {
      match = true
    }
    if (p.length > 1 && p[1] == '*') {
      return match && isMatch(s.slice(1), p) || isMatch(s, p.slice(2))
    } else {
      return match && isMatch(s.slice(1), p.slice(1))
    }
  }