日期:2021年9月22日标签:Algorithm/Math

正则表达式匹配 #

一.题目 #

题目来源于leetcodeRegular Expression Matching:

Given an input string s and a pattern p, implement regular expression matching with support for '.' and '*' where:

  1. . Matches any single character.​​​​
  2. * Matches zero or more of the preceding element. The matching should cover the entire input string (not partial).

翻译:

给定一个字符串s和正则表达式p,实现正则表达式中的.*匹配功能:

  1. . 匹配任意单个字符。
  2. * 匹配0个或者多个该字符前面的字符。 匹配应该是正确匹配输入的完整字符串而非字符串的一部分。

例子: 1.

输入: s = "aa", p = "a"
输出: false
解释: "a"不匹配"aa"。
输入: s = "aa", p = "a*"
输出: true
解释: '*'表示将前一个字符重复0次或者多次. 因此, 将前面的'a'重复1次, 匹配"aa"。
输入: s = "ab", p = ".*"
输出: true
解释: ".*"重复任意字符0次或者多次。
输入: s = "aab", p = "c*a*b"
输出: true
解释: 重复c0次,重复a一次,p匹配"aab"

二.分析 #

如果没有*,只需要从头到尾遍历即可得出答案,但是因为*的存在,题目的难度成倍增加。

递归方法 #

isMatch(s, p)表示字符串sp是否匹配。

将复杂的情况细化讨论:

  1. sp都为空时,结果为true
  2. s不为空时,p为空时,结果为false
  3. s为空,p长度大于等于2,且p[1]*时,结果等价于判断s是否与p.slice(2)匹配。
  4. s不为空,p长度大于等于2,且p[1]*时,若sp首字母匹配(即(!(s.length === 0) && (s[0] === p[0] || p[0] === "."))),结果等价于判断isMatch(s, p.slice(2)) || isMatch(s.slice(1), p)
  5. s不为空,p长度大于等于2,且p[1]*时,若sp首字母不匹配,即判断isMatch(s, p.slice(2))
  6. p的长度小于2,或者p[1]不等于*时,若sp首字母匹配即判断isMatch(s.slice(1), p.slice(1))
  7. p的长度小于2,或者p[1]不等于*时,若sp首字母匹配,结果为false

通过上述分析,很容易写出以下递归答案:

var isMatch = function (s, p) {
    if (p.length === 0) {
        return s.length === 0;
    }

    var firstMatch = (!(s.length === 0) && (s[0] === p[0] || p[0] === "."));

    if (p.length >= 2 && p[1] === "*") {
        return (isMatch(s, p.slice(2)) || (firstMatch && isMatch(s.slice(1), p)));
    } else {
        return firstMatch && isMatch(s.slice(1), p.slice(1));
    }
};

动态规划 #

在上面的递归例子中,其实有大量的计算式重复的。不妨使用动态规划,将已经计算的结果存储起来。

算法思路如下:

  1. 创建一个二维布尔数组dp[s.length() + 1][p.length() + 1]dp[n][m]表示s.slice(0, n)p.slice(0, m)是否匹配,dp[0][0]表示两个空字符串匹配。
  2. 如果s和p都为空,两者匹配,所以dp[0][0]为true,注意这里数组的长度为字符串长度加1,dp[0][0]表示sp为空。
  3. 用一个例子说明,s = "aab"p = "c*a*b",创建一个dp值表:
c*a*b
012345
0TRUEFALSETRUEFALSETRUEFALSE
a1FALSEFALSEFALSETRUETRUEFALSE
a2FALSEFALSEFALSEFALSETRUEFALSE
b3FALSEFALSEFALSEFALSEFALSETRUE
  1. 通过以上表格分析,第一列表示p为空,只有当s也为空时,结果才为true,所以dp[0][0]为true,dp[i][0](i > 0)为false。
  2. 第一行表示s为空时,其中dp[0][2]为true,因为p[2]即p的第二个字符为*,它可以表示重复前面的字符0次,所以dp[0][2]dp[0][0]相等,所以为true
  3. 对于非空字符串,假设s[i - 1] == p[j - 1],这表示第i-1个字符与第j-1个字符相同,也就等价于判断剩余的字符串是否匹配,如果剩余的字符串匹配,那么当前的子字符串也就匹配,否则不匹配,dp[i][j] = dp[i - 1][j-1](注意dp[0][0]表示空字符串,所以1才是字符串的第一个字符)。
  4. 如果p[j - 1] == ".",表示任意单个字符都可以匹配,所以我们需要检查剩余字符是否匹配,即dp[i][j] = dp[i - 1][j - 1]
  5. 如果p[j - 1] == "*",此时有两种情况,第一种情况是重复0次的情况时dp[i][j] == dp[i][j - 2]。第二种情况s[i - 1] == p[j -2] || p[j - 2] == ".",此时dp[i][j] == dp[i - 1][j]

通过以上分析,得到以下解法。 JavaScript:

var isMatch = function (s, p) {
    const rows = s.length;
    const columns = p.length;
    /// Base conditions
    if (rows == 0 && columns == 0) {
        return true;
    }
    if (columns == 0) {
        return false;
    }
    // 创建数组,首列都为false(匹配模式为空)
    const dp = Array.from({ length: s.length + 1 }, () => [false]);
    // 都为空的情况
    dp[0][0] = true;
    // 处理*
    for (let i = 1; i < columns + 1; i++) {
        if (p[i - 1] === '*') {
            dp[0][i] = dp[0][i - 2];
        }
        else {
            dp[0][i] = false;
        };
    }
    // 剩余字符串
    for (let i = 1; i < rows + 1; i++) {
        for (let j = 1; j < columns + 1; j++) {
            if (p[j - 1] === '*') {
                if (p[j - 2] === s[i - 1] || p[j - 2] === '.') {
                    dp[i][j] = dp[i][j - 2] || dp[i - 1][j];
                } else {
                    dp[i][j] = dp[i][j - 2];
                }
            } else if (p[j - 1] === s[i - 1] || p[j - 1] === '.') {
                dp[i][j] = dp[i - 1][j - 1];
            } else {
                dp[i][j] = false;
            }
        }
    }
    return dp[rows][columns];
};

时间复杂度:O(m x n),m表示s的长度,n表示字p的长度。 空间复杂度:O(m × n),m表示s的长度,n表示字p的长度。

(完)

目录