线性动态规划-正则表达式匹配

问题描述

给定两个字符串：s（源字符串）和 p（模式字符串）。模式字符串 p 可以包含两种特殊字符：

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

你的任务是实现一个支持这两种特殊字符的正则表达式匹配函数，以检查源字符串 s 是否与模式 p 匹配。匹配的定义是，可以通过适当地重复 p 中的 * 字符后面的元素（包括不重复），来使 s 完全匹配 p。

示例 1：

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

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

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

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

输入：s = "mississippi" p = "mis*is*p*."
输出：false

注意点

• 需要考虑 * 在模式串中的特殊作用，即它可以表示它前面字符的任意重复次数（包括零次）。
• . 字符可以表示任何字符，但只能代表一个字符。
• 正则表达式应该匹配整个源字符串 s，而不是其中的一部分。

代码实现：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40

/**************************************************************** 
 * Description: 动态规划 正则表达式匹配
 * Author: Alex Li
 * Date: 2023-11-20 18:11:47
 * LastEditTime: 2023-11-20 23:26:02
****************************************************************/
#include <iostream>
#include <string>
#include <vector>
using namespace std;

bool isMatch(string s, string p) {
    int m = s.length(), n = p.length();
    vector<vector<bool> > dp(m + 1, vector<bool>(n + 1, false));
    dp[0][0] = true;

    for (int i = 1; i <= n; ++i) {
        if (p[i - 1] == '*') {
            dp[0][i] = dp[0][i - 2];
        }
    }

    for (int i = 1; i <= m; ++i) {
        for (int j = 1; j <= n; ++j) {
            if (p[j - 1] == '.' || p[j - 1] == s[i - 1]) {
                dp[i][j] = dp[i - 1][j - 1];
            } else if (p[j - 1] == '*') {
                dp[i][j] = dp[i][j - 2] || (dp[i - 1][j] && (p[j - 2] == '.' || p[j - 2] == s[i - 1]));
            }
        }
    }
    return dp[m][n];
}

int main() {
    string s = "aab";
    string p = "c*a*b";
    cout << (isMatch(s, p) ? "Match" : "No Match") << endl;
    return 0;
}

算法思想：

动态规划表 dp

• dp 是一个二维布尔数组，其大小为 (m+1) x (n+1)，其中 m 和 n 分别是字符串 s 和模式 p 的长度。
• dp[i][j] 表示 p 的前 j 个字符是否与 s 的前 i 个字符匹配。

初始化

• dp[0][0] = true：当两个字符串都为空时，它们自然是匹配的。
• 对于模式中的每个字符，如果它是 *，那么我们检查它之前的两个字符是否匹配（因为 * 可以表示零个或多个前一个字符）。这是通过 dp[0][i] = dp[0][i - 2] 实现的。

填充动态规划表

对于每个字符的组合（即对于 s 中的每个字符和 p 中的每个字符），我们按以下规则填充 dp 表：

• 如果 p 的当前字符是普通字符或 .，并且它与 s 的当前字符匹配（对于 .，它匹配任何字符），那么 dp[i][j] 的值取决于去掉这两个字符之前字符串的匹配状态，即 dp[i - 1][j - 1]。

如果 p 的当前字符是 *，则有两种情况：
dp[i][j] = dp[i][j – 2] || (dp[i – 1][j] && (p[j – 2] == ‘.’ || p[j – 2] == s[i – 1]));

• dp[i][j - 2]：* 表示前一个元素出现了零次。
  • 这意味着我们需要忽略 * 及其之前的字符。
  • 例如，如果 p 是 "a*b"，当我们考虑到 * 时，我们需要检查 "b" 是否匹配，即忽略 "a*"。
  • dp[i][j - 2] 检查当我们从模式中去掉 * 及其之前的字符时，是否匹配。
• (dp[i - 1][j] && (p[j - 2] == '.' || p[j - 2] == s[i - 1]))：* 表示前一个元素出现一次或多次。
  • 这种情况下，我们需要检查两个条件：
    • dp[i - 1][j]：这表示如果不考虑 s 的当前字符，p 是否与 s 的剩余部分匹配。这相当于检查 * 表示其之前的元素至少出现一次的情况。
    • (p[j - 2] == '.' || p[j - 2] == s[i - 1])：这检查 * 之前的元素是否匹配 s 的当前字符。p[j - 2] 是 * 之前的字符，它必须是 .（匹配任何字符）或与 s[i - 1] 相同。
• 将这两种情况结合起来，我们得到 dp[i][j] 的值。如果任一情况为真，dp[i][j] 就为真，这意味着 p 的前 j 个字符与 s 的前 i 个字符匹配。