_1190. Reverse Substrings Between Each Pair of Parentheses.md

1190. Reverse Substrings Between Each Pair of Parentheses

All prompts are owned by LeetCode. To view the prompt, click the title link above.

Back to top

---

First completed : July 11, 2024

Last updated : July 11, 2024

---

Related Topics : String, Stack

Acceptance Rate : 71.657 %

---

Solutions

• m1190 Daily v1 O(n^2).py
• m1190 Daily v2 O(1) Wormholes.py

Python

m1190 Daily v1 O(n^2).py

class Solution:
    def reverseParentheses(self, s: str) -> str:
        openingIndices = []
        indx = 0
        output = list(s)

        for indx, c in enumerate(s) :
            if c == '(' :
                openingIndices.append(indx)
            elif c == ')' :
                lastOpen = openingIndices.pop()
                output[lastOpen + 1 : indx] = reversed(output[lastOpen + 1 : indx])

        return ''.join([x for x in output if x != '(' and x != ')'])

m1190 Daily v2 O(1) Wormholes.py

class Solution:
    def reverseParentheses(self, s: str) -> str:
        brackets = []
        bracketPairs = {}

        # Get bracket locations and pair them with their "counterparts"
        for i, c in enumerate(s) :
            if c == ')' :
                left = brackets.pop()
                bracketPairs[left] = i
                bracketPairs[i] = left
            elif c == '(' :
                brackets.append(i)

        # Wormhole travels
        incr = 1
        indx = 0
        output = []
        while indx < len(s) :
            if indx in bracketPairs :
                indx = bracketPairs[indx]
                incr *= -1
            else :
                output.append(s[indx])
            indx += incr

        return ''.join(output)