一. 题目描述1.1 题干信息给出一个字符串 s仅含有小写英文字母和括号。请你按照从括号内到外的顺序逐层反转每对匹配括号中的字符串并返回最终的结果。注意您的结果中 不应 包含任何括号。1.2 示例输入s “(abcd)”输出“dcba”输入s “(u(love)i)”输出“iloveu”解释先反转子字符串 “love” 然后反转整个字符串。输入s “(ed(et(oc))el)”输出“leetcode”解释先反转子字符串 “oc” 接着反转 “etco” 然后反转整个字符串。1.3 提示1 ≤ s . l e n g t h ≤ 2000 1 \le s.length \le 20001≤s.length≤2000s 中只有小写英文字母和括号题目测试用例确保所有括号都是成对出现的二. 储备知识——栈2.1 参考视频这个栈的知识算是数据结构的很基础的内容了我当初是跟着王道学的数据结构所以没有其他的参考视频如果有需要的话可以参考王道bilibili教学视频链接如下:王道计算机考研 数据结构三. 出师不利3.1 初步想法最开始的确看到括号的匹配问题想到的就是栈的应用但是由于我用的是python, 所以懒得直接写栈了第一想法就是用双指针去匹配括号一个从前往后走一个从后往前走代码如下classSolution:defreverseParentheses(self,s:str)-str:front0rearlen(s)-1whilerear0:ifs[front])ands[rear](:ss[:rear1]s[front-1:rear:-1]s[front:]rear-1front-1elifs[front])ands[rear]!(:rear-1elifs[front]!)ands[rear](:front1else:rear-1front1# print(s)returns3个测试用例都通过了but出现了一个大bug交答案的时候总是说我index out of range, 怎么可能索引出界啊我看了代码没问题啊。然后我把答错的用例加入了测试用例中开始针对性该代码发现了一个疏忽不是所有的测试用例0号位置都是(“, -1号位置都是”)…嗯好的那就改吧。3.2 缝缝补补classSolution:defreverseParentheses(self,s:str)-str:front0lengthrearlen(s)-1whilerear0andfrontlength:ifs[front])ands[rear](:# print(fs[rear1: front] is {s[rear1: front]})# print(fs[front-1:rear:-1] is {s[front-1:rear:-1]})ss[:rear1]s[front-1:rear:-1]s[front:]# s[rear1: front] s[front-1:rear:-1]ss[:rear]s[rear1:front]s[front1:]rear-1front-1elifs[front])ands[rear]!(:rear-1elifs[front]!)ands[rear](:front1else:rear-1front1lengthlen(s)-1# print(s)returns这回感觉没问题了加了双指针的越界检测(好吧我是真的不规范正常用双指针就得直接把范围越界测试先写上)信心满满啊交卷嗯。。。解答错误这又为啥原来她这个两个对应的括号未必是全是一个覆盖一个的诶嘿夹带点私货听没听说过闭区间套定理那我给你介绍一下吧哈哈哈哈哈哈T h e o r e m \mathcal{Theorem}Theorem1.5.2 闭区间套定理设I n [ a n , b n ] ( n ∈ N ) I_n[a_n, b_n](n\in\mathbb{N}_{})In​[an​,bn​](n∈N​), 并且I 1 ⊃ I 2 ⊃ I 3 ⊃ ⋯ ⊃ I n ⊃ I n 1 ⊃ ⋯ I_1\supset I_2\supset I_3\supset\cdots\supset I_{n}\supset I_{n1}\supset\cdotsI1​⊃I2​⊃I3​⊃⋯⊃In​⊃In1​⊃⋯. 如果这一列区间的长度∣ I n ∣ b n − a n → 0 ( n → ∞ ) |I_n|b_n-a_n\rightarrow 0(n\rightarrow \infty)∣In​∣bn​−an​→0(n→∞), 那么交集⋂ n 1 ∞ I n \bigcap\limits_{n1}^{\infty} I_{n}n1⋂∞​In​含有唯一的一点。——常庚哲、史济怀《数学分析教程》嗯对的并不是所有测试用例都是类似闭区间套的情况所以还得改啊。四. 大获全胜最后能够完整通过所有测试用例的代码如下。classSolution:defreverseParentheses(self,s:str)-str:stacklist()nearest_listlist()top-1nearest-1foritemins:stack.append(item)top1ifitem(:nearest_list.append(top)elifitem):nearestnearest_list[-1]stack[nearest1:top]stack[top-1:nearest:-1]nearest_listnearest_list[:-1]resultforiinstack:ifinotin[(,)]:resultireturnresult五. 官方题解官方题解提供了两套不同的思路咱们一点点看5.1 栈方法首先就是利用栈的思想去进行字符串匹配如下。classSolution:defreverseParentheses(self,s:str)-str:stk[]stringforchins:ifch(:stk.append(string)stringelifch):stringstring[::-1]stringstk.pop()stringelse:stringchreturnstring5.2 预处理括号方法另一个就是利用预处理括号的方法, 如下。classSolution:defreverseParentheses(self,s:str)-str:nlen(s)pair[0]*n stk[]foriinrange(n):ifs[i](:stk.append(i)elifs[i]):jstk.pop()pair[i]j pair[j]i ret[]index0step1whileindexn:ifs[index](ors[index]):indexpair[index]step-stepelse:ret.append(s[index])indexstepreturn.join(ret)官方题解中有个pair列表这个是左右括号进行对应查询的pair[i] j; pair[j] i。实际上就是把左括号indx的值附上右括号反之亦然。确实是个不错的方法我最开始考虑括号对应赋值的想的用字典dict, 但是感觉有点麻烦就没继续思考下去。然后那个ret列表就很有意思题解中有个int变量step, 如果是1的话就正向读如果是-1的话就是负向读然后就能把题干中反反复复的倒置实现出来。六. 写在最后我始终认定一本好书比它的作者更富有智慧他能传达出作者没有意识到的东西。——翁贝托·艾柯