Reverse Substrings Between Each Pair of Parentheses
Patrick LeatonYou are 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 brackets.
Example 1:
Input: s = "(abcd)" Output: "dcba"
Example 2:
Input: s = "(u(love)i)" Output: "iloveu" Explanation: The substring "love" is reversed first, then the whole string is reversed.
Example 3:
Input: s = "(ed(et(oc))el)" Output: "leetcode" Explanation: First, we reverse the substring "oc", then "etco", and finally, the whole string.
Example 4:
Input: s = "a(bcdefghijkl(mno)p)q" Output: "apmnolkjihgfedcbq"
Constraints:
0 <= s.length <= 2000s only contains lower case English characters and parentheses.
The description was taken from https://leetcode.com/problems/reverse-substrings-between-each-pair-of-parentheses/.
#O(N*P) Time, O(N) Space Where N is Characters and P is Pairs of Parentheses
class Solution:
def reverseParentheses(self, s: str) -> str:
stack = [] for char in s:
if char != ")":
stack.append(char)
else:
bucket = []
while stack and stack[-1] != "(":
bucket.append(stack.pop())
stack.pop()
stack += bucket return "".join(stack)For many of these problems which revolve around seeing a closing bracket and having to backtrack for validation of string manipulation purposes, stacks are typically a good candidate.
The reason for this is with stacks, we're easily able to see what value was just put into the stack and retrieve it immediately through a last in, first out design, LIFO.
If we look at this problem, we need to reverse each substring between each pair of closing parentheses. For reversals, stacks play two roles here; a stack can be used to revisit the previous substring up to the previous opening bracket, and stacks can also be used to reverse the previous substring up to the previous bracket.
What we can do is push each character into the stack up until we see a closing bracket. At that point, we will pop each character from the stack into a temporary array, up until we see an opening bracket.
At that point, we will pop the opening bracket off of the stack and add the temporary array back onto the stack, joining these two arrays together, reversing the topmost substring, and joining it with the substring below it.
Once we have finished, we will just need to join the characters within the stack to form a string and return that string.
Let's start by initializing our empty stack.
stack = []
Next, we'll traverse the string.
for char in s:
If the current character isn't a closing bracket, we'll append it to the stack.
if char != ")":
stack.append(char)
Otherwise, we will initialize an empty bucket and while we still have characters in our stack and the topmost character isn't an opening bracket, we will pop each character from the stack and put them into the bucket.
else:
bucket = []
while stack and stack[-1] != "(":
bucket.append(stack.pop())
When we have broken from the loop, we have no more characters to reverse so we will pop the opening bracket from the stack and push the bucket back on.
stack.pop()
stack += bucket
When we have finished traversing the string, we will join the stack characters together to form a string then return that string.
return "".join(stack)