正则表达式匹配 #

一.题目 #

题目来源于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)表示字符串s与p是否匹配。

将复杂的情况细化讨论：

1. 当s和p都为空时，结果为true。
2. 当s不为空时，p为空时，结果为false。
3. 当s为空，p长度大于等于2，且p[1]为*时，结果等价于判断s是否与p.slice(2)匹配。
4. 当s不为空，p长度大于等于2，且p[1]为*时，若s与p首字母匹配（即(!(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]为*时，若s与p首字母不匹配，即判断isMatch(s, p.slice(2))。
6. 当p的长度小于2，或者p[1]不等于*时，若s与p首字母匹配即判断isMatch(s.slice(1), p.slice(1))。
7. 当p的长度小于2，或者p[1]不等于*时，若s与p首字母匹配，结果为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]表示s和p为空。
3. 用一个例子说明，s = "aab"，p = "c*a*b"，创建一个dp值表：

4. 通过以上表格分析，第一列表示p为空，只有当s也为空时，结果才为true，所以dp[0][0]为true，dp[i][0]（i > 0）为false。
5. 第一行表示s为空时，其中dp[0][2]为true，因为p[2]即p的第二个字符为*，它可以表示重复前面的字符0次，所以dp[0][2]与dp[0][0]相等，所以为true。
6. 对于非空字符串，假设s[i - 1] == p[j - 1]，这表示第i-1个字符与第j-1个字符相同，也就等价于判断剩余的字符串是否匹配，如果剩余的字符串匹配，那么当前的子字符串也就匹配，否则不匹配，dp[i][j] = dp[i - 1][j-1]（注意dp[0][0]表示空字符串，所以1才是字符串的第一个字符）。
7. 如果p[j - 1] == "."，表示任意单个字符都可以匹配，所以我们需要检查剩余字符是否匹配，即dp[i][j] = dp[i - 1][j - 1]。
8. 如果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的长度。

（完）