题目描述

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

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

所谓匹配，是要涵盖 整个 字符串 s的，而不是部分字符串。

来源，leetcode 每日一题 10. 正则表达式匹配

说明:

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

例如1：

  1. 输入:
  2. s = "aa"
  3. p = "a"
  4. 输出: false
  5. 解释: "a" 无法匹配 "aa" 整个字符串。

例如2

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

例如3

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

解题思路

先通过例子了解一下大体的思路

  1. 以一个例子详解动态规划转移方程：
  2. S = abbbbc
  3. P = ab*d*c
  4. 1. 当 i, j 指向的字符均为字母（或 '.' 可以看成一个特殊的字母）时，
  5.    只需判断对应位置的字符即可，
  6.    若相等，只需判断 i,j 之前的字符串是否匹配即可，转化为子问题 f[i-1][j-1].
  7.    若不等，则当前的 i,j 肯定不能匹配，为 false.
  9.        f[i-1][j-1]   i
  10.             |        |
  11.    S [a  b  b  b  b][c] 
  13.    P [a  b  *  d  *][c]
  14.                      |
  15.                      j
  18. 2. 如果当前 j 指向的字符为 '*'，则不妨把类似 'a*', 'b*' 等的当成整体看待。
  19.    看下面的例子
  21.             i
  22.             |
  23.    S  a  b [b] b  b  c  
  25.    P  a [b  *] d  *  c
  26.             |
  27.             j
  29.    注意到当 'b*' 匹配完 'b' 之后，它仍然可以继续发挥作用。
  30.    因此可以只把 i 前移一位，而不丢弃 'b*', 转化为子问题 f[i-1][j]:
  32.          i
  33.          | <--
  34.    S  a [b] b  b  b  c  
  36.    P  a [b  *] d  *  c
  37.             |
  38.             j
  40.    另外，也可以选择让 'b*' 不再进行匹配，把 'b*' 丢弃。
  41.    转化为子问题 f[i][j-2]:
  43.             i
  44.             |
  45.    S  a  b [b] b  b  c  
  47.    P [a] b  *  d  *  c
  48.       |
  49.       j <--
  51. 3. 冗余的状态转移不会影响答案，
  52.    因为当 j 指向 'b*' 中的 'b' 时, 这个状态对于答案是没有用的,
  53.    原因参见评论区 稳中求胜 的解释, 当 j 指向 '*' 时,
  54.    dp[i][j]只与dp[i][j-2]有关, 跳过了 dp[i][j-1].

具体的正式详解如下：

代码

class Solution {
public:
    bool isMatch(string s, string p) {
        int m = s.size();
        int n = p.size();

        auto matches = [&](int i, int j) {
            if (i == 0) {
                return false;
            }
            if (p[j - 1] == '.') {
                return true;
            }
            return s[i - 1] == p[j - 1];
        };

        vector<vector<int>> f(m + 1, vector<int>(n + 1));
        f[0][0] = true;
        for (int i = 0; i <= m; ++i) {
            for (int j = 1; j <= n; ++j) {
                if (p[j - 1] == '*') {
                    f[i][j] |= f[i][j - 2];
                    if (matches(i, j - 1)) {
                        f[i][j] |= f[i - 1][j];
                    }
                }
                else {
                    if (matches(i, j)) {
                        f[i][j] |= f[i - 1][j - 1];
                    }
                }
            }
        }
        return f[m][n];
    }
};