力扣-10. 正则表达式匹配（Regular Expression Matching）

最后编辑于2025-06-07

10. 正则表达式匹配（Regular Expression Matching）

Hard

给定输入字符串 s 和模式 p，实现支持 . 与 * 的正则表达式匹配，其中：

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

匹配应该覆盖整个输入字符串（不是部分匹配）。

示例 1：

输入： s = "aa", p = "a"
输出： false

示例 2：

输入： s = "aa", p = "a*"
输出： true

示例 3：

输入： s = "ab", p = ".*"
输出： true

约束：

  • 1 <= s.length <= 20
  • 1 <= p.length <= 20
  • s 仅包含小写英文字母
  • p 仅包含小写英文字母、. 与 *，且每个 * 前都有合法的字符

思路概览

此题的核心在于处理 * 带来的“零次或多次”匹配，以及 . 的通配符效果。常见解法有：

  • 递归（回溯）：按模式逐步匹配，遇到 * 分支为“使用 0 次”或“使用至少 1 次（并继续匹配）”，直观但会有大量重复计算，可能超时。
  • 动态规划（DP）：构造 dp[i][j] 表示 s[0..i) 与 p[0..j) 是否匹配，状态转移要考虑 * 的 0 次或多次两种情况，复杂度可控且常用于通过 OJ。下面给出三种实现（递归与 DP）。

方法一：递归（带短路的回溯）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    bool isMatch(string s, string p) {
        if (p.empty()) return s.empty();
        if (p.size() == 1) {
            return (s.size() == 1 && (s[0] == p[0] || p[0] == '.'));
        }
        if (p[1] != '*') {
            if (s.empty()) return false;
            return (s[0] == p[0] || p[0] == '.') && isMatch(s.substr(1), p.substr(1));
        }
        // p[1] == '*'
        while (!s.empty() && (s[0] == p[0] || p[0] == '.')) {
            if (isMatch(s, p.substr(2))) return true; // '*' 表示 0 次
            s = s.substr(1); // '*' 表示多次，尝试消费 s 的首字符
        }
        return isMatch(s, p.substr(2)); // '*' 表示 0 次
    }
};
  • 说明： 实现直观，但对某些输入会重复大量子问题，可能超时。

方法二：更紧凑的递归（易超时）

1
2
3
4
5
6
7
8
9
10
11
12
// Time Limit Exceeded
class Solution {
public:
    bool isMatch(string s, string p) {
        if (p.empty()) return s.empty();
        if (p.size() > 1 && p[1] == '*') {
            return isMatch(s, p.substr(2)) || (!s.empty() && (s[0] == p[0] || p[0] == '.') && isMatch(s.substr(1), p));
        } else {
            return !s.empty() && (s[0] == p[0] || p[0] == '.') && isMatch(s.substr(1), p.substr(1));
        }
    }
};

方法三：动态规划（推荐）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    bool isMatch(string s, string p) {
        int m = s.size(), n = p.size();
        vector<vector<bool>> dp(m + 1, vector<bool>(n + 1, false));
        dp[0][0] = true;
        for (int i = 0; i <= m; ++i) {
            for (int j = 1; j <= n; ++j) {
                if (j > 1 && p[j - 1] == '*') {
                    // '*' 表示 0 次或多次
                    dp[i][j] = dp[i][j - 2] || (i > 0 && (s[i - 1] == p[j - 2] || p[j - 2] == '.') && dp[i - 1][j]);
                } else {
                    dp[i][j] = i > 0 && dp[i - 1][j - 1] && (s[i - 1] == p[j - 1] || p[j - 1] == '.');
                }
            }
        }
        return dp[m][n];
    }
};
  • 时间复杂度： O(m * n)
  • 空间复杂度： O(m * n)

作者想说的话：
处理含 * 的正则匹配要么用回溯分支枚举（直观但易重复），要么用 DP 消除重叠子问题。掌握 DP 的状态转移是通过此题的关键。