正则表达式匹配的核心是根据预设的模式规则，判断目标字符串是否符合规则要求。递归回溯算法通过递归遍历模式串和目标串的每个字符，在遇到特殊通配符时尝试多种匹配分支，若当前分支无法匹配则回溯到上一个分支点重新尝试，最终得到匹配结果。
递归回溯算法核心原理
我们实现的正则表达式支持两种特殊规则：'.' 匹配任意单个字符，'*' 匹配零个或多个前面的元素。算法的核心逻辑如下：
- 若模式串当前字符不是
'*'，则判断当前字符是否匹配（相等或为'.'），匹配则递归处理下一个字符，否则返回匹配失败 - 若模式串当前字符是
'*'，则分为两种分支：一是匹配零个前面的元素，跳过模式和'*'处理后续模式；二是若当前字符匹配，则目标串后移一位，模式串保持不变继续尝试匹配 - 递归终止条件：模式串遍历完成时，若目标串也遍历完成则匹配成功，否则失败
C++源码实现
以下是完整的C++实现代码，包含匹配逻辑和测试示例：
#include <iostream>
#include <string>
using namespace std;
// 递归回溯匹配函数
// s: 目标字符串，p: 正则表达式模式
bool isMatch(string s, string p) {
// 模式串为空的情况
if (p.empty()) {
return s.empty();
}
// 判断当前第一个字符是否匹配
bool firstMatch = (!s.empty() && (p[0] == s[0] || p[0] == '.'));
// 处理带*的情况
if (p.size() >= 2 && p[1] == '*') {
// 分支1：匹配0个前面的元素，跳过p的前两个字符
// 分支2：当前字符匹配，s后移一位，p保持不变继续匹配
return (isMatch(s, p.substr(2)) || (firstMatch && isMatch(s.substr(1), p)));
} else {
// 非*情况，当前字符匹配则都后移一位
return firstMatch && isMatch(s.substr(1), p.substr(1));
}
}
int main() {
// 测试用例
cout << isMatch("aa", "a") << endl; // 输出0，不匹配
cout << isMatch("aa", "a*") << endl; // 输出1，匹配
cout << isMatch("ab", ".*") << endl; // 输出1，匹配
cout << isMatch("aab", "c*a*b") << endl; // 输出1，匹配
cout << isMatch("mississippi", "mis*is*p*.") << endl; // 输出0，不匹配
return 0;
}
代码逻辑解析
上述代码中，isMatch 函数为核心递归函数，首先处理模式串为空的基本情况。当模式串长度大于等于2且第二个字符是 '*' 时，进入分支处理逻辑：第一种分支尝试匹配零个前面的元素，直接跳过模式和 '*' 递归处理剩余模式；第二种分支在当前字符匹配的前提下，目标串后移一位，模式串保持不变，继续尝试匹配更多相同字符。
如果模式串第二个字符不是 '*'，则判断当前字符是否匹配，匹配则两个串都后移一位递归处理，否则直接返回失败。递归的终止条件是模式串为空时，判断目标串是否也为空，为空则匹配成功。
算法复杂度分析
递归回溯算法的时间复杂度在最坏情况下为指数级，因为每次遇到 '*' 都会产生两个递归分支。空间复杂度取决于递归调用的深度，最坏情况下递归深度等于目标串的长度，因此空间复杂度为 O(n)，n 为目标串的长度。
适用场景说明
这种递归回溯实现适合处理简单的正则匹配需求，仅支持 '.' 和 '*' 两种规则，对于复杂的正则语法（如分组、断言等）无法支持。如果需要更完整的正则匹配能力，建议使用标准库中的 regex 组件，或者成熟的第三方正则库。