Description
Reverse Substrings Between Each Pair of Parentheses
MediumYou 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.
Solutions
This solution uses an explicit stack of string buffers plus a single boolean rev that flips every time a parenthesis is crossed, so rev is true exactly when the current text sits inside an odd number of parentheses. The helper appendStr writes to the top of the stack in one of two ways: when rev is false it appends to the end (stack[top] += str), and when rev is true it prepends to the front (str + stack[top]), which builds the segment backwards without ever calling a reverse function. On ( the code pushes a fresh empty buffer and toggles rev; on ) it toggles rev back first and then pops the finished inner segment and merges it into the new top using the same helper, so the parent's own orientation decides how the child is attached; any other character is simply passed to appendStr. When the loop ends, only the base buffer remains and stack[0] is the fully transformed string.
/**
* @param {string} s
* @return {string}
*/
var reverseParentheses = function(s) {
const stack = [''];
let rev = false;
const appendStr = (str) => {
if (!rev) {
stack[stack.length - 1] += str;
} else {
stack[stack.length - 1] = str + stack[stack.length - 1];
}
};
for (const char of s) {
if (char === '(') {
stack.push('');
rev = !rev;
} else if (char === ')') {
rev = !rev;
appendStr(stack.pop());
} else {
appendStr(char);
}
}
return stack[0];
};