1. 从一道竞赛题看正则表达式与搜索算法的结合正则表达式在很多人印象里就是用来做字符串匹配的工具写几行模式串就能完成复杂的文本筛选。但你可能没想到正则表达式本身也可以被当作一棵树来解析而解析这棵树的过程恰好是深度优先搜索的经典应用场景。蓝桥杯历届试题里就有这么一道“正则问题”它把正则表达式的语法规则和DFS的递归思想揉在一起既考察对正则语义的理解也考察递归搜索的编码能力。这道题的核心任务是给定一个只包含x、|、(、)四种字符的正则表达式求出这个表达式能够匹配的字符串中最长的那个字符串的长度。换句话说我们要算出这个正则表达式所描述的语言里最长字符串的长度是多少。这里的正则语法被简化了x表示一个字符|表示或运算()表示分组没有*、、?这些量词。所以整个表达式描述的是一个有限的字符串集合我们要找的是其中长度最大的那个。适合谁来参考这篇内容如果你正在准备蓝桥杯或者类似的算法竞赛对DFS、递归、栈这些概念有一定了解但还不够熟练那这道题非常适合拿来练手。它不需要复杂的图论建模也不需要高级数据结构核心就是递归搜索加状态维护。但它的坑也不少尤其是括号嵌套和或运算的优先级处理稍不注意就会写错。下面我会从整体思路、核心细节、完整实现、常见问题几个方面把这道题彻底拆开讲清楚。2. 整体思路与方案选型拆解2.1 为什么这道题要用DFS而不是其他方法拿到这道题第一反应可能是用栈来模拟。毕竟括号匹配、表达式求值这类问题栈是很自然的工具。但仔细想想这道题要求的是“最长匹配长度”而不是“求值”或者“判断是否匹配”。在或运算|的分支处我们需要同时考虑左右两边的情况取最大值。这种“在分支处探索所有可能性并取最优”的需求天然适合递归搜索。用栈的话你需要在栈里维护每个分组内的当前最大值和候选值遇到|时要保存当前状态并重置遇到)时要合并状态。逻辑上可行但状态管理会非常复杂尤其是多层嵌套括号时栈里需要保存的信息会越来越多。而递归的好处是每一层递归自然对应一层括号函数返回时自动完成状态合并代码结构清晰得多。再对比一下动态规划。这道题能不能用DP理论上可以但状态定义会很麻烦。因为正则表达式的结构是嵌套的不是线性的DP的状态转移需要考虑括号的嵌套关系反而比递归更复杂。所以综合来看递归DFS是这道题最自然、最简洁的解法。2.2 递归函数的设计思路核心思路是这样的定义一个递归函数dfs()它的作用是解析从当前位置开始的一段正则表达式直到遇到)或者字符串结束为止返回这段表达式能匹配的最长字符串长度。在函数内部我们需要维护两个变量current表示当前正在累积的这一段由x和括号组成的分组的长度best表示到目前为止所有分支中的最大值。为什么需要两个变量因为|的优先级最低它把整个表达式分成若干分支每个分支内部是若干x和括号的拼接。所以我们需要先算出每个分支的长度然后取所有分支的最大值。具体来说遍历字符串的每一个字符遇到x当前分支长度加一即current。遇到(递归调用dfs()把返回的长度加到current上。因为括号内的内容是一个整体它的长度就是括号内表达式的最长匹配长度。遇到|说明当前分支结束了把current和best比较取较大值存入best然后重置current为0开始计算下一个分支。遇到)说明当前括号内的表达式结束了先做一次best max(best, current)然后返回best。字符串遍历结束时同样做一次best max(best, current)然后返回best。这个逻辑看起来简单但有几个关键点容易出错。第一|的处理时机是在遇到|时更新best并重置current而不是在遇到)时才处理。第二括号递归返回后返回值是加到current上而不是直接和best比较。第三字符串结束时也要更新一次best否则最后一个分支会被遗漏。2.3 或运算的优先级与分支处理或运算的优先级是这道题的核心难点之一。在正则表达式中|的优先级最低它把整个表达式分成若干分支。比如xx|xxx|x表示三个分支xx、xxx、x最长的是xxx长度为3。而x(x|xx)x则表示x后面跟一个分组分组内有两个分支x和xx最后再跟一个x。这个表达式能匹配的最长字符串是xxx即xxxx长度为4。注意这里的区别在xx|xxx|x中|分割的是整个表达式而在x(x|xx)x中|只作用于括号内部。这就是为什么递归函数在遇到)时要返回因为它只负责解析当前括号内的内容外层的拼接由外层函数处理。理解这一点之后代码的逻辑就清晰了。每次遇到(就进入一层新的递归这层递归只关心括号内的表达式遇到对应的)就返回。返回的值代表括号内表达式的最长匹配长度这个长度作为一个整体加到外层的current上。3. 核心细节解析与实操要点3.1 递归函数的参数与返回值设计在写递归函数时参数设计很关键。这道题有两种常见的写法一种是把字符串和当前位置的索引作为参数传递另一种是用全局变量维护索引。两种写法都可以但各有优劣。传参写法dfs(s, i)返回一个元组(最长长度, 新索引)表示从索引i开始解析返回解析结果和解析结束后的位置。这种写法的好处是状态清晰不依赖外部变量但每次返回都要处理元组代码稍显繁琐。全局索引写法用一个全局变量pos表示当前解析到的位置dfs()不需要参数直接返回最长长度。这种写法代码更简洁但需要注意pos的更新时机尤其是在递归调用和遇到)时。我个人更推荐全局索引写法因为这道题的递归逻辑本身就不复杂用全局索引可以让代码更聚焦于核心逻辑。但要注意pos在递归调用前后要正确维护。具体来说遇到(时先pos跳过左括号然后递归调用递归返回后pos已经指向)的位置再pos跳过右括号。3.2 括号嵌套时的状态隔离括号嵌套是这道题最容易出错的地方。考虑表达式((xx|xxx)x|(x|xx))xx这个表达式有多层嵌套每层都有自己的|和x。在递归解析时每一层递归函数都有自己的current和best变量这些变量是局部的不会互相干扰。这正是递归的优势所在。但有一个细节需要注意当递归函数遇到)返回时它返回的是当前括号内的最长匹配长度。这个返回值会被外层函数加到current上。也就是说括号内的表达式被当作一个整体它的长度就是返回值。外层函数不需要知道括号内具体是怎么分组的只需要知道最长长度是多少。这种“黑盒”式的处理方式正是递归分治思想的体现。每一层只关心自己这一层的逻辑嵌套的细节交给内层递归处理。这样代码才能保持简洁不容易出错。3.3 边界情况的处理技巧这道题有几个边界情况需要特别注意第一种是空表达式。虽然题目通常不会给空字符串但理论上如果输入为空最长匹配长度应该是0。在代码里如果字符串遍历结束best和current都是0返回0即可不需要特殊处理。第二种是只有x的情况。比如输入xxx没有|也没有括号。这时current会累加到3遍历结束后best max(0, 3) 3返回3正确。第三种是只有|的情况。比如输入x|x|x三个分支长度都是1最终返回1。代码逻辑是遇到第一个|时best max(0, 1) 1current重置为0遇到第二个|时best max(1, 1) 1current重置为0遍历结束时best max(1, 1) 1返回1。正确。第四种是括号内为空的情况。比如x()x这种表达式在题目给定的语法下可能不会出现但如果出现了递归函数遇到)时直接返回0外层current加0相当于括号不存在。这种处理方式是合理的。注意在实际写代码时建议先处理)的情况再处理|的情况最后处理x和(的情况。因为)和|都涉及到状态更新和返回顺序搞错容易导致逻辑混乱。4. 完整实现与关键步骤说明4.1 代码框架与全局变量定义下面给出完整的C实现。选择C是因为蓝桥杯主要使用C而且C的递归写起来比较直观。如果你习惯用Python或Java逻辑完全一样只是语法不同。#include iostream #include string #include algorithm using namespace std; string s; int pos 0; // 全局索引表示当前解析到的位置 int dfs() { int current 0; // 当前分支的长度 int best 0; // 所有分支中的最大值 while (pos s.size()) { char c s[pos]; if (c x) { current; pos; } else if (c () { pos; // 跳过左括号 current dfs(); // 递归解析括号内的内容 // 递归返回后pos已经指向右括号 } else if (c )) { pos; // 跳过右括号 best max(best, current); return best; } else if (c |) { pos; // 跳过或运算符 best max(best, current); current 0; // 重置当前分支长度 } } // 字符串遍历结束更新best best max(best, current); return best; } int main() { cin s; cout dfs() endl; return 0; }这段代码的核心就是dfs()函数。全局变量pos维护当前解析位置current和best是局部变量每层递归都有自己的副本。遇到(时递归调用遇到)时返回遇到|时更新best并重置current遇到x时累加current。4.2 逐步跟踪执行过程用一个具体例子来跟踪代码的执行过程这样能更清楚地理解递归的工作方式。假设输入是x(xx|xxx)x。初始状态pos 0调用dfs()。第一层递归pos 0字符是xcurrent 1pos 1。pos 1字符是(pos 2递归调用dfs()。第二层递归pos 2字符是xcurrent 1pos 3。pos 3字符是xcurrent 2pos 4。pos 4字符是|best max(0, 2) 2current 0pos 5。pos 5字符是xcurrent 1pos 6。pos 6字符是xcurrent 2pos 7。pos 7字符是xcurrent 3pos 8。pos 8字符是)pos 9best max(2, 3) 3返回3。回到第一层递归current 1 3 4pos 9。pos 9字符是xcurrent 5pos 10。pos 10字符串结束best max(0, 5) 5返回5。最终输出5。验证一下x(xx|xxx)x的最长匹配是xxxxxxxxxx长度为5正确。4.3 时间与空间复杂度分析时间复杂度方面每个字符最多被访问一次递归调用的总次数等于括号的对数。所以整体时间复杂度是 O(n)其中 n 是字符串长度。这个复杂度非常优秀对于蓝桥杯的题目规模来说完全够用。空间复杂度方面递归的深度等于括号的最大嵌套层数。最坏情况下如果字符串是((((...))))这种形式递归深度为 n/2空间复杂度为 O(n)。对于通常的题目规模这个空间开销是可以接受的。实操心得在写递归函数时建议先用小规模的例子手动跟踪一遍确认逻辑正确后再提交。这道题的逻辑虽然不复杂但括号和或运算的组合容易让人绕晕手动跟踪能帮你快速定位问题。5. 常见问题与排查技巧实录5.1 为什么我的代码在嵌套括号时结果不对这是最常见的问题。嵌套括号出错通常是因为递归返回后没有正确处理pos的位置。具体来说当递归函数遇到)返回时pos已经指向了)的位置。外层函数在递归调用返回后需要确保pos已经跳过了)否则外层函数会再次遇到)导致逻辑混乱。在上面的代码中递归函数在遇到)时执行了pos所以返回后pos已经指向)的下一个字符。外层函数不需要再做任何处理直接继续循环即可。如果你在递归返回后又执行了一次pos就会跳过一个字符导致结果错误。另一种常见错误是在递归调用前没有跳过(。如果pos指向(时直接递归递归函数第一眼看到的就是(会再次进入递归导致无限递归。所以必须在递归调用前执行pos跳过(。5.2 或运算分支合并时的陷阱或运算的处理是另一个容易出错的地方。关键是要理解|分割的是当前层的分支而不是整个表达式的分支。在递归函数中每次遇到|都要把当前的current和best比较取较大值存入best然后重置current。这样做的目的是在遇到下一个|或)或字符串结束时best已经保存了之前所有分支的最大值。如果你在遇到|时忘记更新best那么最后一个分支之前的所有分支都会被忽略。比如xx|xxx|x如果只在字符串结束时更新best那么best只会是最后一个分支的长度1而不是3。所以每次遇到|都必须更新best。还有一个细节在遇到)时也要更新一次best。因为括号内的最后一个分支可能没有被|触发更新。比如(xx|xxx)遇到|时更新了best 2然后current累加到3遇到)时如果不更新best就会返回2而不是3。所以)处的best max(best, current)是必须的。5.3 常见问题速查表问题现象可能原因排查方法解决方案结果偏小最后一个分支未更新检查字符串结束时是否更新best在while循环后加best max(best, current)结果偏大括号返回值重复累加检查递归返回后是否重复处理确保递归返回后不再执行pos无限递归左括号未跳过检查递归调用前是否pos在递归调用前执行pos跳过(嵌套括号结果错误pos位置未正确维护手动跟踪pos的变化确保递归返回后pos指向)的下一个字符或运算结果错误best更新时机不对检查每次遇到和)时是否更新best5.4 独家避坑技巧第一个技巧在写代码之前先用纸笔画出表达式的树形结构。每个|是一个分支节点每个()是一个子树每个x是一个叶子节点。画出树之后递归的逻辑就一目了然了。这个方法看起来笨但能帮你快速理清思路避免在代码里绕晕。第二个技巧如果实在不确定递归逻辑是否正确可以先写一个暴力解法。对于小规模的输入暴力枚举所有可能的匹配字符串取最长长度。然后用暴力解法验证递归解法的结果。虽然暴力解法在比赛时不能用但用来调试和验证是非常有效的。第三个技巧注意输入字符串可能包含空格或换行。虽然题目通常不会这么坑但保险起见可以在读入后去掉所有空白字符。C里可以用getline读入整行然后用erase和remove去掉空格。提示这道题的递归深度可能很大如果字符串长度达到10^5级别递归可能会导致栈溢出。但在蓝桥杯的题目规模下通常不会这么极端。如果担心栈溢出可以把递归改成显式栈的迭代写法但代码会复杂很多。6. 从这道题延伸出的通用解题思路6.1 递归解析嵌套结构的通用模式这道题展示了一种处理嵌套结构的通用模式遇到左边界如(时递归进入遇到右边界如)时返回结果中间的过程由当前层的逻辑处理。这种模式不仅适用于正则表达式解析还适用于很多其他场景比如解析JSON、计算数学表达式、处理HTML标签等。核心思想是每一层递归只关心自己这一层的逻辑嵌套的细节交给内层递归处理。内层递归返回的结果被当作一个整体外层不需要知道内层的具体实现。这种分治思想是递归解题的精髓。在实际写代码时关键是要明确三个问题什么时候进入递归遇到左边界、什么时候返回遇到右边界、返回值是什么当前层的结果。把这三个问题想清楚代码就不会写错。6.2 状态维护与回溯的取舍这道题的递归函数不需要回溯因为每次递归调用都是独立的内层递归的结果直接加到外层的current上不需要撤销。但在其他一些DFS题目中回溯是必须的比如全排列、子集生成等。什么时候需要回溯当你在搜索过程中修改了共享状态并且需要在搜索结束后恢复状态时就需要回溯。这道题的状态是局部的每层递归有自己的current和best不会互相干扰所以不需要回溯。理解这一点很重要因为很多初学者会习惯性地在递归调用前后加“保存状态”和“恢复状态”的代码但这道题不需要。加了反而可能出错。所以写递归时先想清楚状态是共享的还是局部的再决定是否需要回溯。6.3 类似题目的练习建议如果你想巩固这道题的知识点可以尝试以下几类练习第一类是括号匹配类题目比如判断括号是否合法、计算括号嵌套深度等。这类题目和正则问题共享“递归处理嵌套结构”的核心思想。第二类是表达式求值类题目比如计算加减乘除表达式、处理带括号的布尔表达式等。这类题目在递归的基础上增加了运算符优先级的处理难度稍高。第三类是树形结构遍历类题目比如二叉树的深度、路径和等。这类题目和递归解析嵌套结构在思路上是相通的都是把大问题分解成子问题。我个人在实际练习中的体会是递归类题目不要贪多做一道就要彻底搞懂一道。每道题做完后试着用不同的方式实现一遍比如把全局索引改成参数传递或者把递归改成迭代。这样能加深对递归本质的理解遇到新题时也能更快找到思路。