本文共 2135 字，大约阅读时间需要 7 分钟。

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

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

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

示例 1：

输入：s = "(abcd)"输出："dcba"

示例 2：

输入：s = "(u(love)i)"输出："iloveu"

示例 3：

输入：s = "(ed(et(oc))el)"输出："leetcode"

示例 4：

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

提示：

• 0 <= s.length <= 2000
• s 中只有小写英文字母和括号
• 我们确保所有括号都是成对出现的

解题思路

之前碰到的类似问题，直接使用dfs不再赘述。

class Solution:    def reverseParentheses(self, s: str) -> str:        i = 0        def dfs():            nonlocal i            res = ""            while i < len(s):                if s[i] == '(':                    i += 1                    res += dfs()                elif s[i] == ')':                    return res[::-1]                else:                    res += s[i]                i += 1            return res                return dfs()

当然也可以使用栈来做，栈中存放字符串。

• 如果我们碰到的元素是(的时候，我们需要向栈中添加一个空字符串
• 如果我们碰到的元素是)的时候，我们需要将栈中最后一个字符串反转，然后添加到倒数第二个字符串中

class Solution:    def reverseParentheses(self, s: str) -> str:        res = ['']        for c in s:            if c == '(':                res.append('')            elif c == ')':                res[len(res) - 2] += res.pop()[::-1]            else:                res[-1] += c        return "".join(res)

但是上面这些做法其实都是O(n^2)的，有没有更快的解法呢？有，我们可以先记录所有配对括号的位置（通过字典实现）。

( u ( l o v e ) i )↑      →

当我们碰到(的时候，我们通过字典直接跳到与之匹配的)，然后从后向前遍历。

( u ( l o v e ) i )           ←      ↑

接着当我们碰到)的时候，我们通过字典直接跳到与之匹配的(，并且此时遍历的方向需要反向。

( u ( l o v e ) i )    ↑     →

将此时遍历的字符串添加到结果中去即可。

class Solution:    def reverseParentheses(self, s: str) -> str:        st, pair = [], {
   }        for i, c in enumerate(s):            if c == '(':                st.append(i)            if c == ')':                j = st.pop()                pair[i], pair[j] = j, i                        res, i, d = "", 0, 1        while i < len(s):            if s[i] in '()':                i = pair[i]                d = -d            else:                res += s[i]            i += d        return res

此时算法的时间复杂度优化到了O(n)。

reference:

https://leetcode.com/problems/reverse-substrings-between-each-pair-of-parentheses/discuss/383670/JavaC%2B%2BPython-Why-not-O(N)

我将该问题的其他语言版本添加到了我的

如有问题，希望大家指出！！！

转载地址：https://coordinate.blog.csdn.net/article/details/100915900 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！