1190. Reverse Substrings Between Each Pair of Parentheses

https://leetcode.com/problems/reverse-substrings-between-each-pair-of-parentheses/

Reverse Substrings Between Each Pair of Parentheses - LeetCode

부분 부분 서브스트링이 소괄호로 감싸져있는데,

가장 안쪽 스트링 부터 reverse 시키면서 소괄호를 벗기는 문제

 

계산하기 편하도록 쪼갠 뒤,

stack을 이용해서 넣으며, )를 만나는 순간 (를 찾아가며 소괄호를 벗겨나간다.

 

28~32ms

class Solution:
    def reverseParentheses(self, s: str) -> str:
        
        splited = []
        buf = []
        for c in s:
            if c == '(' or c == ')':
                if buf:
                    splited.append(''.join(buf))
                splited.append(c)
                buf = []
            else:
                buf.append(c)
        
        if buf:
            splited.append(''.join(buf))
        
        stack = []
        
        for item in splited:
            if item == ')':
                tmp = []
                while True:
                    if stack[-1] == '(':
                        stack.pop()
                        break
                    else:
                        tmp.append(stack.pop())
                tmp = ''.join(tmp[::-1])[::-1]
                stack.append(tmp)
            else:
                stack.append(item)
        
        return ''.join(stack)

20 ms

class Solution:
    def reverseParentheses(self, s: str) -> str:
        chars = []
        def reverse(l, r):
            while l < r:
                chars[l], chars[r] = chars[r], chars[l]
                l += 1
                r -= 1
        
        stack = []
        for char in s:
            if char == '(':
                stack.append(len(chars))
            elif char == ')':
                reverse(stack.pop(), len(chars) - 1)
            else:
                chars.append(char)
        return ''.join(chars)