Leetcode 1190. 反转每对括号间的子串(medium)

本文主要是介绍Leetcode 1190. 反转每对括号间的子串(medium)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目

给出一个字符串 s（仅含有小写英文字母和括号）。

请你按照从括号内到外的顺序，逐层反转每对匹配括号中的字符串，并返回最终的结果。

注意，您的结果中 不应 包含任何括号。

示例 1：

输入：s = "(abcd)"
输出："dcba"
示例 2：

输入：s = "(u(love)i)"
输出："iloveu"
解释：先反转子字符串 "love" ，然后反转整个字符串。
示例 3：

输入：s = "(ed(et(oc))el)"
输出："leetcode"
解释：先反转子字符串 "oc" ，接着反转 "etco" ，然后反转整个字符串。
示例 4：

输入：s = "a(bcdefghijkl(mno)p)q"
输出："apmnolkjihgfedcbq"

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/reverse-substrings-between-each-pair-of-parentheses
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

解题思路

1.原始解法

首先需要注意的是，题目所给出的示例有一定的迷惑性。实际上每对括号有可能相继出现，而非一定互相嵌套，如有一个测试用例大致为ts()usw((a))。在这种情况下，使用栈是一种比较简单的解题方式。

思路为每次读入一个字符，如果是)，则取出上一个(之后的所有内容，进行翻转，推回栈。

结果：通过测试用例，用时40ms，内存消耗15MB

代码：

class Solution: def reverseWithinParentheses(self, s):position = s.rfind("(")string_to_reverse = s[position + 1:]new_string = s[:position]new_string += string_to_reverse[::-1]return new_stringdef reverseParentheses(self, s: str) -> str:answer = "" # stackfor e in s:if e == ')':answer = self.reverseWithinParentheses(answer)else:answer += ereturn answer

相关知识

1.栈

这篇关于Leetcode 1190. 反转每对括号间的子串(medium)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---