C++正则表达式匹配
目录
1. 正则表达式介绍
2. 分析思考
2.1 动态规划简介
2.2 实现思路
3. 伪代码实现
4. 代码实现
5. 结果展示
6. 可能的踩坑点
1. 正则表达式介绍
正则表达式（Regular Expression，简称 regex 或 regexp）是一种用于匹配字符串中特定模式的工具。它是一种强大且灵活的文本处理技术，广泛应用于编程、文本编辑、数据验证等领域。正则表达式由一系列字符和特殊符号组成，这些字符和符号定义了搜索模式。通过使用正则表达式，可以快速地在文本中查找、替换、提取符合特定规则的字符串。
1.1 实现案例
考虑如下要求：
实现一个支持 '.' 和 '' 的正则表达式匹配。其中 '.' 匹配任意单个字符，'' 匹配零个或多个前面的元素。匹配需要覆盖整个字符串 s，而非部分字符串。
2. 分析思考
这个问题可以使用动态规划来解决，我们先来看下动态规划是什么，以及怎么做动态规划。（了解的同学可以先跳过）
2.1 动态规划简介
动态规划（Dynamic Programming，简称 DP）是一种用于解决复杂问题的算法设计方法。它通过将问题分解为更小的子问题，并存储这些子问题的解，从而避免重复计算，提高效率。
动态规划 通常适用于具有以下两个性质的问题 ：
- 重叠子问题 ：问题可以分解为若干个子问题，且这些子问题之间存在重叠。
- 最优子结构 ：问题的最优解可以通过子问题的最优解来构造。
动态规划的标准流程 常常包括以下步骤：
- 定义状态 ：明确问题的状态是什么，通常用一个或多个变量来表示。
- 初始化 ：确定初始状态的值。
- 状态转移方程 ：描述如何从一个状态转移到另一个状态，通常通过递推关系来表示。
- 计算顺序 ：确定计算状态的顺序，通常是自底向上或自顶向下。
- 返回结果 ：根据最终状态返回问题的解。
2.2 实现思路
了解了上面的内容后，我们可以根据动态规划的思路，先定义一个二维数组 dp[i][j]，表示字符串 s 的前 i 个字符和模式 p 的前 j 个字符是否匹配。
-
初始化 ：空字符串和空模式是匹配的（dp[0][0] = true）。对于空字符串，需处理模式中可能存在如 a* 的结构。
-
状态转移 ：
- 当模式字符不是 '*' 时，直接比较字符是否匹配，并参考之前的匹配结果。
- 当模式字符是 '' 时，有两种情况：匹配零次（忽略前一个字符和 ''）或匹配多次（需当前字符匹配前一个模式字符）。
-
计算顺序 ：从左到右、从上到下填充dp表。
-
返回结果 ：dp[m][n]就是最终的匹配结果。
3. 伪代码实现
初始化 dp[0][0] = true
处理空字符串的情况：
遍历模式 p 的每个字符，若当前字符是 '*'，则更新 dp[0][j] = dp[0][j-2]
遍历每个字符 i 和 j：
若 p[j-1] 不是 '*'：
若字符匹配（相等或 '.'），则 dp[i][j] = dp[i-1][j-1]
否则：
处理 '*' 的情况：
零次匹配：dp[i][j] = dp[i][j-2]
若当前字符匹配前一个模式字符，则 dp[i][j] |= dp[i-1][j]
返回 dp[m][n]
4. 代码实现
#include <vector>
#include <string>
using namespace std;
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;
// 处理空字符串的情况，初始化p中的'*'
for (int j = 1; j <= n; ++j) {
if (p[j-1] == '*' && j >= 2) {
dp[0][j] = dp[0][j-2];
}
}
for (int i = 1; i <= m; ++i) {
for (int j = 1; j <= n; ++j) {
// 当前模式字符不是'*'
if (p[j-1] != '*') {
if (p[j-1] == '.' || s[i-1] == p[j-1]) {
dp[i][j] = dp[i-1][j-1];
}
} else {
// 处理'*'的情况，需要至少两个字符
if (j >= 2) {
// 零次匹配
dp[i][j] = dp[i][j-2];
// 一次或多次匹配，检查当前字符是否匹配前一个模式字符
if (p[j-2] == '.' || p[j-2] == s[i-1]) {
dp[i][j] = dp[i][j] || dp[i-1][j];
}
}
}
}
}
return dp[m][n];
}
};
5. 结果展示
示例 1：s = "aa", p = "a" → false。模式无法匹配整个字符串。
示例 2：s = "aa", p = "a*" → true。a* 匹配两个 a。
示例 3：s = "ab", p = "." → true。. 匹配任意字符。
6. 可能的踩坑点
初始化处理：空字符串的匹配需正确处理模式中的 a* 结构。
状态转移条件：处理 '' 时，需考虑零次和多次匹配，且多次匹配需当前字符与前一个模式字符匹配。
边界条件：题目保证 '' 前必有有效字符，无需处理无效输入。