[10] 正则表达式匹配

给你一个字符串 s 和一个字符规律 p，请你来实现一个支持 '.' 和 '*' 的正则表达式匹配。

'.' 匹配任意单个字符 '*' 匹配零个或多个前面的那一个元素 所谓匹配，是要涵盖 整个 字符串 s的，而不是部分字符串。

说明:

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

示例 1:

输入:

s = "aa"

p = "a"

输出: false

解释: "a" 无法匹配 "aa" 整个字符串。

示例 2:

输入:

s = "aa"

p = "a*"

输出: true

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

示例 3:

输入:

s = "ab"

p = ".*"

输出: true

解释: ".*" 表示可匹配零个或多个（'*'）任意字符（'.'）。

示例 4:

输入:

s = "aab"

p = "c*a*b"

输出: true

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

示例 5:

输入:

s = "mississippi"

p = "mis*is*p*."

输出: false

这道题是让我们实现一个简单的正则表达匹配，我们有两种方法来解。

递归法

先从比较容易想到的递归法来思考这个问题。

首先我们可以将题目简化为递归的判断两字符串是否相等，这样的递归式很好推：f(s, p) = string[i] === pattern[i] && f(s-1, p-1)。

这里需要注意结束递归的条件为：当两个字符串都为空时，返回true。并且若其中一个为空而另一个不为空时，返回false。

之后我们在考虑加上.匹配符。.能匹配任何字符，我们只需要稍微将递归式变动一下：f(s,p) = (pattern[i] === '.' || string[i] === pattern[i]) && f(s-1, p-1)，即可满足条件。

接下来就是难点*匹配符，它能将前一个字符匹配0个或若干个。首先可以看出，正则合法的条件是：*前面必须有一个字符，即剩余的pattern.length >= 2。之后我们需要分两种情况考虑：

1. 匹配0个。这种情况下我们只需要去掉*与前面的字符并继续匹配即可。f(s, p) = f(s, p-2)。
2. 匹配若干次。由于我们在这里使用的是递归，因此匹配多次即可以转化为多次匹配1次的算法，因此我们从匹配1次的情况考虑。那情况跟没有*运算符是一致的：如果*前的一个字符匹配，则继续下一次递归，否则直接返回false。但是这里要注意递归条件不同了，因为这里可能被*匹配多次，因此*运算符应当被保留，知道匹配0次的时候再去除。因此递推式为：f(s,p) = (pattern[i] === '.' || string[i] === pattern[i]) && f(s-1, p)。

由此我们就能写出改题的解了。

var isMatch = function(s, p) {
  return isPatternMatch(s, p);
}

function isPatternMatch(string, pattern) {
  const lens = string.length;
  const lenp = pattern.length;
  if (lens === 0 && lenp === 0) return true;
  if ((lens !== 0 && lenp === 0) || (lens === 0 && lenp !== 0)) return false;

  const firstMatch = pattern[0] === '.' || string[0] === pattern[0];

  if (lenp >= 2 && pattern[1] === '*') {
    const isNoneMatch = isPatternMatch(string, pattern.substring(2));
    const isOnceMatch = firstMatch && isPatternMatch(string.substring(1), pattern);
    return isOnceMatch || isNoneMatch;
  }
  return firstMatch && isPatternMatch(string.substring(1), pattern.substring(1));
};

动态规划

这道题可以也尝试着用dp来解。一般来说，涉及到两字符串比较求极值的问题，通常都是建立一个二维数组dp[i][j]，然后让两字符串的每个字符充当横纵轴，然后查看结果是否匹配。

这里需要特别注意的是，我们在定义dp时考虑了空字符串的问题，因此横纵长度分别+1，要注意遍历时i/j与字符串中字符的对应关系：dp[i][j]应该对应s[i-1]与p[i-1]。定义好问题后，我们看下子问题分类，这里一共有两种情况。

1. 当正则字符串的当前字符不为*时，那么就考虑s前一个字符是否被p前一个字符匹配了(即相等或.)，子问题化简为dp[i-1][j-1]。即当dp[j-1] !== "*"时：dp[i][j] = dp[i-1][j-1] && s[i-1] === p[j-1] || p[j-1] === '.'

2. 当正则字符串的当前字符为*时，子问题又要分化为两种情况，即：

   1. 在*前面的字符没有被匹配过，那么匹配字符串的前两个字符都可以被去掉了。即当*前一个的字符没有被匹配过时：dp[i][j] = dp[i][j-2] 当dp[j-1] === "*"

   2. 在*前面的字符被匹配过，那么就考虑s前一个字符是否与p前第二个字符匹配(即相等或.)(因为p前一个字符为*)，即当*前面的字符被匹配过时：dp[i][j] = dp[i-1][j]

function isMatch(s: string, p: string): boolean {
  const dp: boolean[][] = Array(s.length + 1)
    .fill(0)
    .map(x => Array(p.length + 1).fill(false));
  dp[0][0] = true;
  for (let i = 0; i <= s.length; i++) {
    for (let j = 1; j <= p.length; j++) {
      if (j >= 2 && p[j - 1] === '*') {
        // 当*前的一个字符未被匹配时，那么匹配字符串p的前两个字符都可以被去掉了
        const isNoneMatch = dp[i][j - 2];
        // 若p中*的前一个字符被s当前字符匹配上，则认为匹配，结果与去除s当前字符的情况相同
        const isOnceMatch = i >= 1 && (s[i - 1] === p[j - 2] || p[j - 2] === '.') ? dp[i - 1][j] : false;
        dp[i][j] = isNoneMatch || isOnceMatch;
      } else {
        // 将s与p的当前字符作比对，如相符或者p中字符为.通配符，则结果与dp[i-1][j-1]相同
        const isMatch = i >= 1 && (s[i - 1] === p[j - 1] || p[j - 1] === '.') ? dp[i - 1][j - 1] : false;
        dp[i][j] = isMatch;
      }
    }
  }
  return dp[s.length][p.length];
}