Regular Expression Indepth
from leetcode
自己用写了一个丐版的 主要问题就在于 * 如何匹配
怎么说呢
“.”这个玩意我觉得可以 直接str[++i]，但是在一起的话 .* 没办法
当时实现的时候没考虑到存 str.peek() 尽可能不用递归的我哭晕在厕所
这道题准确写完个人觉得 不应该使用 所谓什么的动态规划
说实话 我看到 leetcode 上面默认是 cpp 就绷不住了 高人一等...?
从现代cpp视角来看....似乎....有点不太对吧？
注意：我说的是工程的cpp，与cpp标准无关....
核心写的思路： * 我认为可以这么想：
直到下一个str[i]与need_to_regex[i-1] is =
但是有个问题就在于 * 有可能匹配的是 none
我不想用递归 纯循环+goto 没想出来
qwen3 说我可以
bool first_match = (*s != '\0') && (*s == *p || *p == '.');
if (*(p + 1) == '*') {
// 两种情况：
// 1. '*' 匹配0个字符：跳过 "x*"，继续匹配剩余部分
// 2. '*' 匹配1个或多个字符：当前字符匹配且字符串继续匹配
return (isMatch(s, p + 2)) ||
(first_match && isMatch(s + 1, p));
} else {
// 没有 '*'，则逐字符匹配
return first_match && isMatch(s + 1, p + 1);
}
我是觉得有点难想的，我想直接出来解决问题而不是复杂问题...
后面这个ai还贴心告诉我说你可以用dp来查表做规划...
牛逼，这是为了解决递归stack的问题... sicp 讲过 这个“治表不治根”
bool isMatchHelper(char* s, int i, char* p, int j, int s_len, int p_len) {
// 如果已经计算过，直接返回结果
if (visited[i][j]) {
return dp[i][j];
}
+ modify (first_match && isMatchHelper(s, i + 1, p, j, s_len, p_len));
+ modify result = first_match && isMatchHelper(s, i + 1, p, j + 1, s_len, p_len);
visited[i][j] = true;dp[i][j] = result;
return result;
dp 怎么说呢 我是真的不想用 典型用空间换时间 是 递归的副产品 不是 这道题目的
直接解法
但是ai 指出来我的小细节：EOF文件的处理(所有表达式都有可能!)
还有 当俩个字符串都是空的时候 也是匹配的哈哈哈哈(我是觉得没必要，lc买你的课去)
谁没事干用vim / 一下出来所有文字是吧？
我的意思是，没人跟你耗在这里，考虑太全面，我希望有点多方法看问题
Beautiful code is likely to be simple
qwen3 吐给我的 有意思的文章 里面给出了一个比较完整的 regex parser
但是考虑的是 “最短代码”
有点像递归下降了..
Rob Pike’s simple C regex matcher in Go
Go 更有意思一点 好像更短了哈哈哈哈...
Regular Expression Matching Can Be Simple And Fast
这个就是我想要的那种 但是是手工模拟的pop&&push
怎么说
完全没问题 而且效率还可以 但是 更难想了
还确实难想 是这样说 Ken Thompson都发了一篇小通讯的小难度做优化算法..
反正我就是这么想的：肯定要用编译原理的知识 不然我们是题目的附庸
真的得多读读代码
似乎归来还是递归哈哈哈哈哈哈 但是我懒得 直接看NFA DFA吧~