难度: 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"
提示：
1 <= s.length <= 2000s 中只有小写英文字母和括号运行时间: 20 ms
内存: 0.0 MB
class Solution:
def reverseParentheses(self, s: str) -> str:
stack=[]
ans=""
for c in s:
if c==")":
k=stack.pop(-1)
tp=""
while k!="(":
tp+=k
k=stack.pop(-1)
for t in tp:
stack.append(t)
else:
stack.append(c)
for c in stack:
ans+=c
return ans
本题解采用栈的数据结构来处理括号内的字符串反转。遍历输入字符串s的每个字符，对于每个非右括号字符，直接压入栈中。当遇到右括号时，开始从栈中弹出字符，直到遇到左括号为止，将这些字符（即左括号内的字符串）进行反转并再次压入栈中。这样，当遇到右括号时，栈中的字符串被反转。最后，将栈中的字符依次弹出，拼接成最终的结果字符串。
时间复杂度: O(n)
空间复杂度: O(n)
class Solution:
def reverseParentheses(self, s: str) -> str:
stack = [] # 用来存储字符和部分反转的字符串
for c in s:
if c == ')':
tp = ''
# 弹出元素直到遇到'('
while stack and stack[-1] != '(':
tp += stack.pop()
stack.pop() # 弹出'('
# 将反转后的字符串再压入栈中
for t in tp:
stack.append(t)
else:
stack.append(c) # 将非')'的字符压入栈中
# 将栈中的所有字符合并为结果字符串
return ''.join(stack)
在算法实现过程中，通常需要额外的逻辑来确保括号匹配。例如，可以在遍历输入字符串时，对每个遇到的左括号进行计数，并对每个右括号进行相应的减少计数。如果在任何时刻右括号的数量超过左括号的数量，或者在遍历结束后左括号的数量不为零，则说明括号不匹配。在实际编码过程中，这可以通过抛出异常或返回特定的错误信息来处理。
处理嵌套深度较深的括号结构时，算法的时间复杂度主要由字符串的长度决定，为O(n)，其中n是字符串的长度。每个字符最多被压入和弹出栈一次。尽管嵌套的深度可能影响局部操作的复杂度（如需要连续多次弹出栈中的字符），但总体时间复杂度仍为O(n)。在实际应用中，栈的深度（即括号的嵌套深度）可能影响到空间复杂度，但这通常不会超过字符串的长度。
在Python中，字符串是不可变的，这意味着每次使用`+=`操作实际上会创建一个新的字符串并复制旧字符串的内容，导致O(n^2)的时间复杂度。更高效的处理方法是使用列表来收集字符，然后在需要的时候使用`''.join()`方法来连接列表中的字符。这样做的时间复杂度为O(n)，因为每个字符只被复制一次。
虽然栈中的字符顺序在处理过程中已经是最终的顺序，但它们依旧是以单个字符形式存储在列表中。Python中的字符串是不可变类型，因此不能直接修改字符串的内容。使用`''.join(stack)`是将列表中的所有字符合并成一个单一的字符串对象，这是从列表到字符串转换的标准方法，同时也是效率较高的操作。