Medium

题目描述

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

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

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

示例 1：

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

示例 2：

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

示例 3：

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

提示：

  • 1 <= s.length <= 2000
  • s 只含有小写英文字符和括号
  • 题目测试用例确保所有括号都是成对出现的

解题思路

解题思路

这道题要求我们从最内层的括号开始，逐层向外反转字符串。有两种主要的解法：

方法一：栈模拟（推荐）

使用栈来模拟括号匹配过程：

  1. 遍历字符串，将字符逐个压入栈中
  2. 遇到左括号 ( 时，直接压栈作为分隔符
  3. 遇到右括号 ) 时，从栈中弹出字符直到遇到对应的左括号，将这些字符反转后重新压入栈中
  4. 最后栈中剩余的就是结果字符串

方法二：预处理 + 双向遍历

通过预处理找到每个括号的配对位置，然后根据当前遍历方向决定是正向还是反向移动指针。这种方法空间复杂度更优，但实现稍复杂。

栈方法更直观易懂，是面试中的首选方法。

代码实现

class Solution {
public:
    string reverseParentheses(string s) {
        stack<char> st;
        
        for (char c : s) {
            if (c == ')') {
                string temp = "";
                while (!st.empty() && st.top() != '(') {
                    temp += st.top();
                    st.pop();
                }
                st.pop(); // 弹出 '('
                for (char ch : temp) {
                    st.push(ch);
                }
            } else {
                st.push(c);
            }
        }
        
        string result = "";
        while (!st.empty()) {
            result = st.top() + result;
            st.pop();
        }
        
        return result;
    }
};

class Solution:
    def reverseParentheses(self, s: str) -> str:
        stack = []
        
        for c in s:
            if c == ')':
                temp = []
                while stack and stack[-1] != '(':
                    temp.append(stack.pop())
                stack.pop()  # 弹出 '('
                stack.extend(temp)
            else:
                stack.append(c)
        
        return ''.join(stack)

public class Solution {
    public string ReverseParentheses(string s) {
        Stack<char> stack = new Stack<char>();
        
        foreach (char c in s) {
            if (c == ')') {
                List<char> temp = new List<char>();
                while (stack.Count > 0 && stack.Peek() != '(') {
                    temp.Add(stack.Pop());
                }
                stack.Pop(); // 弹出 '('
                foreach (char ch in temp) {
                    stack.Push(ch);
                }
            } else {
                stack.Push(c);
            }
        }
        
        char[] result = new char[stack.Count];
        for (int i = stack.Count - 1; i >= 0; i--) {
            result[i] = stack.Pop();
        }
        
        return new string(result);
    }
}

/**
 * @param {string} s
 * @return {string}
 */
var reverseParentheses = function(s) {
    let stack = [''];
    
    for (let char of s) {
        if (char === '(') {
            stack.push('');
        } else if (char === ')') {
            let top = stack.pop();
            stack[stack.length - 1] += top.split('').reverse().join('');
        } else {
            stack[stack.length - 1] += char;
        }
    }
    
    return stack[0];
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型栈方法
时间复杂度O(n)
空间复杂度O(n)

其中 n 为字符串长度。虽然看似有嵌套循环，但每个字符最多被处理常数次，所以总体时间复杂度仍为 O(n)。