剑指Offer题解 - Day64

剑指 Offer 19. 正则表达式匹配

力扣题目链接

请实现一个函数用来匹配包含'. '和'*'的正则表达式。模式中的字符'.'表示任意一个字符，而'*'表示它前面的字符可以出现任意次（含0次）。在本题中，匹配是指字符串的所有字符匹配整个模式。例如，字符串"aaa"与模式"a.a"和"ab*ac*a"匹配，但与"aa.a"和"ab*a"均不匹配。

「示例 1:」

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

「示例 2:」

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

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

分析：

总的思路应该是这样的：

• 从s[1]和p[1]开始判断，每轮添加一个字符并判断是否能匹配，直至添加完整个字符串s和p。
• 如果s[1-i]和p[1-i]是匹配的，那么添加下一个字符会出现两种情况：
  • 添加字符s[i + 1]是否匹配？
  • 添加字符p[i + 1]是否匹配？
• 由此可见，此题可以使用动态规划求解。

问题来到了动态规划转移方程如何确定。

首先，我们规定dp[i][j]代表字符串 s 的前 i 个字符和 p 的前 j 个字符能否匹配。

由于 dp[0][0]代表的是空字符的状态， 因此 dp[i][j]对应的添加字符是 s[i - 1]和 p[j - 1]。dp[i][j] 要想成立，取决于p[j - 1] 是否为* ，因为表示匹配零个或多个字符。

• 当p[j - 1] === '*' 时，以下情况为true时，dp[i][j] 为true。
  • dp[i][j - 2] 。那么p[j - 2]p[j - 1] 就相当于p[j - 2]* 。此时*意味着出现0次。那么p[j - 2] 出现0次，就是匹配的。
  • dp[i - 1][j] 且 s[i - 1] === p[j - 2] ****。那么p[j - 2]p[j - 1] 就相当于p[j - 2]p[j - 2] ，此时* 意味着多出现一次，就是匹配的。
  • dp[i - 1][j] 且 p[j - 2] === '.' ****。那么p[j - 2]p[j - 1] 就相当于.. ，此时* 意味着多出现一次，就是匹配的。
• 当p[j - 1] !== '*'时，以下情况为true时，dp[i][j] 为true。
  • dp[i - 1][j - 1]且s[i - 1] === p[j - 1] 。意味着s[i - 2] === p[i - 2]且s[i - 1] === p[i - 1] ，那么此时肯定是相等的。
  • dp[i - 1][j - 1]且p[j - 1] = '.' ****。意味着p[j - 1] 可以是任意字符，当然可以是s[i - 1] ，那么此时就是匹配的。

总的来看，通过判断p的最后一个字符是否等于'*' ，来决定如何转移状态。当等于'*' 时，因为可以出现零次或者多次，所以需要判断上个字符p[j - 2]与上一个状态的关系。当不等于'*' 时，需要判断当前字符p[j - 1]与s[i - 1] 的关系。

还需要初始化dp矩阵首行，防止状态转移索引越界。

• dp[0][0] = true。也就是说两个空字符串是可以匹配的。
• dp[0][j] = dp[0][j - 2] 且 p[j - 1] === '*'。因为首行 s为空字符串，因此当 p 的偶数位为 * 时才能够匹配。此时* 意味着前面的字符出现0次，也就是p的奇数位出现0次。所以将p的偶数位置为* 。

最后返回矩阵右下角字符即可。

动态规划

/**
 * @param {string} s
 * @param {string} p
 * @return {boolean}
 */
var isMatch = function(s, p) {
    const m = s.length + 1;
    const n = p.length + 1;
    const dp = Array.from({ length: m }, () => Array.from({ length: n }).fill(false));
    dp[0][0] = true;
    for(let j = 2; j < n; j += 2) {
        dp[0][j] = dp[0][j - 2] && p[j - 1] === '*';
    }
    for(let i = 1; i < m; i++) {
        for(let j = 1; j < n; j++) {
            if (p[j - 1] === '*') {
                dp[i][j] = dp[i][j - 2] || dp[i - 1][j] && (s[i - 1] === p[j - 2] || p[j - 2] === '.')
            } else {
                dp[i][j] = dp[i - 1][j - 1] && (s[i - 1] === p[j - 1] || p[j - 1] === '.')
            }
        }
    }
    return dp[m - 1][n - 1];
};

• 时间复杂度 O(mn)。
• 空间复杂度 O(mn)。

总结

本题考查动态规划的应用。难度系数是困难。本题的难点在于如果转义状态。通过判断p的最后一个字符是否为* ，衍生出两种状态。

复杂度方面，需要遍历整个dp矩阵，因此时间复杂度是O(mn) ，而dp矩阵需要占用额外的O(mn) 空间。