Algorithm
Problem Name: 1190. Reverse Substrings Between Each Pair of Parentheses
You 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.
Constraints:
1 <= s.length <= 2000sonly contains lower case English characters and parentheses.- It is guaranteed that all parentheses are balanced.
Code Examples
#1 Code Example with Java Programming
Code -
Java Programming
class Solution {
public String reverseParentheses(String s) {
char[] letters = s.toCharArray();
Stack < Integer> stack = new Stack<>();
for (int i = 0; i < s.length(); i++) {
if (s.charAt(i) == '(') {
stack.push(i);
} else if (s.charAt(i) == ')') {
reverse(letters, stack.pop(), i);
}
}
StringBuilder sb = new StringBuilder();
for (int i = 0; i < letters.length; i++) {
if (letters[i] == '(' || letters[i] == ')') {
continue;
}
sb.append(letters[i]);
}
return sb.toString();
}
private void reverse(char[] letters, int start, int end) {
while (start < end) {
char temp = letters[start];
letters[start++] = letters[end];
letters[end--] = temp;
}
}
}
Input
s = "(abcd)"
Output
"dcba"
#2 Code Example with Javascript Programming
Code -
Javascript Programming
const reverseParentheses = function(s) {
const res = ['']
let control = 0
let order = 1
for (let i = 0; i < s.length; i++) {
if (s[i] === '(') {
control++
order = order ? 0 : 1
res.push('')
} else if (s[i] === ')') {
if (order) res[control - 1] = res.pop() + res[control - 1]
else res[control - 1] = res[control - 1] + res.pop()
order = order ? 0 : 1
control--
} else {
if (order) res[control] = res[control] + s[i]
else res[control] = s[i] + res[control]
}
}
return res[0]
}
Input
s = "(abcd)"
Output
"dcba"
#3 Code Example with Python Programming
Code -
Python Programming
class Solution:
def reverseParentheses(self, s: str) -> str:
stack = ['']
for c in s:
if c == '(':
stack.append('')
elif c == ')':
add = stack.pop()[::-1]
stack[-1] += add
else:
stack[-1] += c
return stack.pop()
Input
s = "(u(love)i)"
Output
"iloveu"
#4 Code Example with C# Programming
Code -
C# Programming
using System.Collections.Generic;
using System.Linq;
using System.Text;
namespace LeetCode
{
public class _1190_ReverseSubstringsBetweenEachPairOfParentheses
{
public string ReverseParentheses(string s)
{
var stack = new Stack < char>();
foreach (var ch in s)
{
if (ch != ')') stack.Push(ch);
else
{
var sb = new StringBuilder();
while (stack.Peek() != '(')
sb.Append(stack.Pop());
stack.Pop();
foreach (var ch2 in sb.ToString())
stack.Push(ch2);
}
}
return string.Join("", stack.Reverse());
}
}
}
Input
s = "(u(love)i)"
Output
"iloveu"