1. 从一道竞赛题看正则表达式与搜索算法的交汇第一次看到“正则问题”这个题目名很多人会以为要手写一个正则表达式引擎或者调用语言内置的 regex 库去匹配字符串。实际上这道题的核心根本不是正则匹配而是用深度优先搜索去解析一个带有嵌套结构的表达式并求出它能匹配的最长字符串长度。换句话说它考的是“把嵌套的括号结构翻译成一棵搜索树然后在树上做最优决策”的能力。这道题在蓝桥杯历届试题里属于比较经典的一类题目给出一段只包含x、|、(、)四种字符的“正则表达式”其中x表示一个字符|表示或运算括号表示分组。要求你求出这个表达式所能表示的字符串集合中最长字符串的长度。比如xx|xxx的最长匹配长度是 3(xx|xxx)x的最长匹配长度是 4((xx|xxx)x|(x|xx))xx的最长匹配长度是 6。它适合谁来参考如果你正在准备蓝桥杯、ACM 类算法竞赛或者想系统理解 DFS 在“表达式解析”类问题中的落地方式这道题是一个非常好的练手素材。它不需要复杂的动态规划状态设计也不需要图论建模核心就是递归下降 分情况取最优。但恰恰因为结构简单它能把 DFS 的几个关键细节——递归边界、状态传递、分支合并——暴露得非常清楚。我当年第一次做这道题时卡在了“或运算怎么在递归里合并结果”这个点上后来才想明白整个表达式本质上是一棵以|为分支节点、以x为叶子、以括号为子树的树DFS 的任务就是自底向上地计算每个子树能贡献的最大长度。下面我把这道题从思路到实现完整拆一遍包括我踩过的坑和实测有效的调试方法。2. 题目结构拆解与核心思路选型2.1 表达式语法规则到底在说什么先把题目给出的语法用最朴素的话翻译一遍。表达式由四种符号组成x代表一个普通字符贡献长度 1。|代表“或”左右两边任选其一最终长度取两边中较大的那个。(和)代表分组括号内部的整体作为一个单元参与外层运算。表达式可以嵌套也可以连续拼接比如xx表示两个字符依次出现长度累加。这里有一个容易被忽略的点拼接是隐式的。题目里没有专门的连接符号两个相邻的单元放在一起就表示它们要连起来。比如(xx)x表示先匹配xx再匹配x总长度是 3。这一点和很多正则引擎的写法一致但在代码里需要特别处理因为你在扫描字符串时遇到x或(就意味着一新单元的开始而不是等待某个分隔符。理解了语法就能明白这道题要求的东西给定一个表达式求它所有可能匹配结果中长度最大的那个值。注意是“最大长度”不是“匹配某个具体字符串”所以不需要真的生成字符串只需要在解析过程中维护长度信息即可。2.2 为什么选 DFS 而不是栈或动态规划这类嵌套结构的问题常见解法有三种显式栈模拟、递归下降、动态规划区间 DP。我选 DFS 递归下降理由有三条。第一结构天然递归。括号的嵌套和|的分支本质上就是一棵树的递归定义。用递归函数去处理代码结构和问题结构是一一对应的可读性最高。你写一个dfs()函数它的职责就是“从当前位置开始解析一个完整单元返回它能贡献的最大长度”然后遇到括号就递归调用自己遇到|就分别求两边取最大。第二栈模拟容易出错。如果用显式栈你需要手动维护当前层的最大值、当前累计值、遇到|时怎么回退、遇到)时怎么合并到上一层。这些状态在栈里交错调试时非常痛苦。我试过用栈写一版结果在((xx|xxx)x|(x|xx))xx这种多层嵌套上卡了很久最后还是换回递归。第三区间 DP 属于杀鸡用牛刀。区间 DP 需要枚举分割点时间复杂度 O(n³)而这道题 n 最多几百虽然也能过但代码量和思维负担都更大。DFS 递归下降是 O(n) 的每个字符只被访问一次效率更高写起来也更直接。提示递归下降的核心假设是“表达式合法且括号匹配”。这道题题目保证输入合法所以不需要做错误处理。如果是在实际工程里解析用户输入必须加上括号匹配检查和非法字符过滤。2.3 递归函数的设计契约在动手写代码之前先把递归函数的“契约”定清楚这是整个解法最关键的一步。我定义的函数签名是def dfs(s, i): # 从下标 i 开始解析一个单元返回 (最大长度, 下一个待处理位置)为什么返回两个值因为解析完一个单元后你不知道后面还有没有内容需要把“解析到哪了”这个信息传回给调用方。比如解析(xx)x时内层递归处理完xx遇到)返回外层需要知道)后面还有一个x要继续处理。函数内部的逻辑分三层当前层累计值cur记录当前分支下已经拼接的长度。当前层最大值best记录遇到|时之前所有分支里的最大长度。循环扫描遇到x让cur加一遇到|把cur归入best并重置cur遇到(递归求子单元长度并累加到cur遇到)或字符串结束就收尾返回。这个契约一旦定好代码就是水到渠成的事。下面我把完整实现和每一步的意图拆开讲。3. 递归下降的完整实现与逐行拆解3.1 核心代码框架先给出完整可运行的 Python 版本然后逐段解释。import sys def dfs(s, i): cur 0 # 当前分支累计长度 best 0 # 当前层历史最大长度 while i len(s): ch s[i] if ch x: cur 1 i 1 elif ch |: # 遇到或运算把当前分支结算进 best重新开始累计 best max(best, cur) cur 0 i 1 elif ch (: # 递归解析括号内部返回子单元长度和新的位置 sub_len, i dfs(s, i 1) cur sub_len elif ch ): # 当前层结束结算并返回 best max(best, cur) return best, i 1 # 字符串扫描完毕结算最后一分支 best max(best, cur) return best, i def solve(): s sys.stdin.readline().strip() ans, _ dfs(s, 0) print(ans) if __name__ __main__: solve()这段代码不到 40 行但每一行都对应一个明确的语义。下面拆开说。3.2 遇到 x 为什么直接加一x是叶子节点它不产生分支只贡献长度 1。所以在当前分支的累计值cur上加一即可。这里不需要做任何判断因为题目保证x就是单个字符。但有一个细节值得注意连续多个 x 是累加关系。比如xxx的cur会依次变成 1、2、3最后best取 3。这符合“拼接”的语义。3.3 遇到 | 时的结算与重置|是这道题的分支点。它的语义是“左边和右边任选其一”所以当前分支到此为止需要把cur结算进best然后重置cur为 0开始统计右边分支。这里有一个容易写错的地方结算时用的是max(best, cur)而不是直接赋值。因为一个单元里可能有多个|比如x|xx|xxx你需要取所有分支的最大值。我第一次写的时候用了best cur结果只能拿到最后一个分支的长度调试了半天才发现。另外|后面的分支可能不是简单字符而是括号或更复杂的结构所以重置cur后继续循环即可后续遇到(会递归处理遇到x会继续累加。3.4 括号递归的进入与返回遇到(时调用dfs(s, i 1)意思是“从括号内部的下一个字符开始解析一个完整单元”。子递归会在遇到匹配的)时返回返回值有两个子单元的最大长度以及)之后的下一个位置。外层拿到子单元长度后直接累加到cur上。这体现了括号的语义括号内部整体作为一个单元参与外层拼接。比如(xx|xxx)x子递归返回 3外层cur变成 3然后继续处理后面的x最终cur变成 4。这里的关键是位置传递。子递归返回的i已经跳过了)外层循环直接从新位置继续不会重复处理括号内的字符。3.5 遇到 ) 或字符串结束的收尾遇到)时说明当前层解析完毕。需要做两件事把当前cur结算进best然后返回(best, i 1)其中i 1是跳过)后的位置。如果循环自然结束i到达字符串末尾说明没有遇到)但当前层也要收尾同样结算best并返回(best, i)。这两种收尾逻辑本质相同只是返回的位置不同。我在代码里把它们分开写是为了让)的处理更直观。你也可以合并成一个收尾函数但分开写调试时更容易定位问题。3.6 手动模拟一遍执行过程拿(xx|xxx)x这个例子手动走一遍递归栈能帮你彻底理解状态流转。第一层dfs(s, 0)s[0]是(进入子递归dfs(s, 1)。子递归从i1开始s[1]xcur1s[2]xcur2s[3]|bestmax(0,2)2cur0s[4]xcur1s[5]xcur2s[6]xcur3s[7])bestmax(2,3)3返回(3, 8)。外层拿到sub_len3cur3i8。s[8]xcur4i9。循环结束bestmax(0,4)4返回(4, 9)。最终答案 4。这个过程里best在子递归里经历了 0→2→3 的变化最终取 3外层cur从 0→3→4最终取 4。每一步都对应一个明确的语义没有多余的状态。4. 实操中的关键细节与避坑经验4.1 输入读取的坑换行与空格这道题输入只有一行字符串但实际比赛中输入可能带有首尾空格或多余换行。我用sys.stdin.readline().strip()读取strip()会去掉首尾空白但不会影响中间的字符。注意不要用input()因为input()在某些环境下会把\r也读进来导致字符串末尾多一个不可见字符循环时多走一轮。如果你用 C 写建议用getline(cin, s)而不是cin s因为cin s遇到空格会截断虽然这道题输入没有空格但养成习惯更稳妥。4.2 递归深度与栈溢出题目中括号嵌套层数最多可能达到几百层。Python 默认递归深度是 1000一般够用但如果嵌套特别深可能触发RecursionError。保险起见可以在开头加sys.setrecursionlimit(10000)C 的栈空间通常更大但极端情况下也可能溢出。如果不想用递归可以改写成显式栈但代码复杂度会上升不少。我的建议是竞赛环境下优先用递归加一行提高递归深度即可。4.3 或运算的优先级问题这道题的语法里|的优先级低于拼接但高于括号的“分组”语义。换句话说xx|xxx应该理解为(xx)|(xxx)而不是x(x|x)xx。我的递归实现天然满足这个优先级因为|在循环里遇到就结算当前cur而拼接是隐式累加括号是递归处理。但如果你用其他方式实现比如先做词法分析再做语法分析就需要显式定义优先级。这也是我推荐递归下降的原因之一优先级直接体现在代码结构里不需要额外维护优先级表。4.4 空表达式与边界情况题目保证输入合法但实际写代码时最好考虑一下边界。比如输入只有一个x答案是 1输入是()理论上不合法但如果不小心遇到我的代码会返回 0。再比如输入是x|末尾的|后面没有内容我的代码会在循环结束后结算best结果是 1也算合理。这些边界情况在竞赛里通常不会出现但如果你想把代码改成通用解析器就需要加上合法性检查。我的建议是竞赛代码以过题为目标不要过度设计工程代码才需要考虑健壮性。4.5 调试技巧打印递归树递归代码最难的地方是“看不见执行过程”。我调试时会在dfs入口和出口加打印def dfs(s, i): print(fenter dfs at {i}, char{s[i] if i len(s) else END}) # ... 原有逻辑 ... print(fexit dfs at {i}, return {best}) return best, i这样能看到递归的进入和返回顺序配合手动模拟很快就能定位问题。实测下来这道题最常见的 bug 是|结算时忘了取max或者括号返回后位置没有跳过)打印一下就能发现。5. 常见问题排查与扩展思考5.1 常见问题速查表问题现象可能原因排查方法解决方法答案偏小 结算时用了赋值而非取最大检查best max(best, cur)答案偏大括号返回后位置未跳过)打印返回的i值返回i 1死循环递归时位置没有推进检查每次递归i是否变化确保i单调递增栈溢出嵌套层数过深查看报错信息提高递归深度限制结果不稳定输入读取带了不可见字符打印字符串长度和内容用strip()清理5.2 如果题目改成求最短长度怎么办把max全部换成min就行但要注意初始值。best初始应该设为一个很大的数cur初始为 0。遇到|时best min(best, cur)收尾时同样取最小。这个改动很小但能帮你理解“或运算”在最大和最小语义下的对称性。5.3 如果题目改成输出具体字符串怎么办那就不能只维护长度了需要在每个节点记录“当前最优字符串”。递归返回时把子串拼接起来。这会增加内存开销但思路不变。实际比赛中很少这么考因为输出字符串的判定比较麻烦。5.4 如果表达式里加入*和怎么办*表示重复零次或多次表示重复一次或多次。这时候问题就复杂了因为重复次数会影响长度需要引入动态规划或贪心策略。对于*如果内部单元能贡献正长度就无限重复取最大如果贡献 0就取 0。对于至少重复一次。这类扩展在竞赛里属于进阶题核心还是递归下降但状态设计要更细致。5.5 这道题对实际工作的启发虽然这是一道竞赛题但它背后的“递归下降解析”思想在实际工作里非常有用。比如解析配置文件、处理嵌套的 JSON 结构、实现简单的模板引擎都会用到类似的思路。我后来在一个日志分析工具里就用几乎相同的递归结构去解析带括号的过滤表达式代码量很少但可读性和扩展性都很好。注意实际工程里的表达式解析通常需要处理错误输入、支持更多运算符、考虑性能优化。竞赛题的解法是一个很好的起点但不要直接照搬到生产环境。6. 我个人在这道题上的调试体会这道题我前前后后写了三版。第一版用栈模拟卡在多层嵌套的合并逻辑上写了 80 多行还是过不了。第二版改用递归但|结算时用了赋值导致x|xx|xxx只能拿到最后一个分支的长度。第三版才把max和位置传递这两个点理顺最终 30 多行搞定。我的体会是递归下降的关键不在于代码多复杂而在于把函数契约定清楚。只要明确“函数从哪开始、返回什么、位置怎么传递”剩下的就是按语法规则填逻辑。另外手动模拟一遍执行过程比盯着代码看半小时都管用尤其是括号嵌套和|分支交错的时候画个简单的递归树状态流转一目了然。最后分享一个小技巧如果你在比赛里遇到类似的嵌套结构题先别急着写代码拿纸笔把输入串的递归树画出来标出每个节点的返回值和位置。树画清楚了代码就是翻译工作。这个方法我在好几道 DFS 题上都用过实测很稳。