花花酱 LeetCode 1190. Reverse Substrings Between Each Pair of Parentheses

Given a string s that consists of lower case English letters and brackets. 

Reverse the strings in each pair of matching parentheses, starting from the innermost one.

Your result should not contain any bracket.

Example 1:

Input: s = "(abcd)"
Output: "dcba"

Example 2:

Input: s = "(u(love)i)"
Output: "iloveu"

Example 3:

Input: s = "(ed(et(oc))el)"
Output: "leetcode"

Example 4:

Input: s = "a(bcdefghijkl(mno)p)q"
Output: "apmnolkjihgfedcbq"

Constraints:

• 0 <= s.length <= 2000
• s only contains lower case English characters and parentheses.
• It’s guaranteed that all parentheses are balanced.

Solution: Stack

Use a stack of strings to track all the active strings.
Iterate over the input string:
1. Whenever there is a ‘(‘, push an empty string to the stack.
2. Whenever this is a ‘)’, pop the top string and append the reverse of it to the new stack top.
3. Otherwise, append the letter to the string on top the of stack.

Once done, the (only) string on the top of the stack is the answer.

Time complexity: O(n^2)
Space complexity: O(n)