Problem overview
The method reverseParentheses receives a string s made of lowercase letters and balanced parentheses. It must reverse the text inside every pair of matching parentheses, starting with the innermost pair, and return a result that contains no parentheses.
For "(u(love)i)" the inner pair holds love, which becomes evol. The string is now (uevoli). Reversing the outer pair gives iloveu. For "(yme(oc(da))gla)" the order is da, then ocad, then the whole text, and the final answer is algocademy.
Approach: one buffer per nesting level
The obvious plan is to find the innermost pair, reverse it in place, remove its parentheses and repeat. That works, but every round rescans and rebuilds the string, which is slow for deeply nested input.
A stack avoids the repetition. Walk through the string once and keep a stack of buffers, where each buffer is a string. The buffer on top collects the characters of the level we are currently in:
- A letter is appended to the top buffer.
- An opening parenthesis starts a new level, so push an empty buffer.
- A closing parenthesis ends the current level. Pop the top buffer, reverse it, and append the result to the buffer below, which is the level that contained the pair.
The innermost pair always closes first, so its text is reversed first, and that reversed text is then part of its parent's buffer, which is reversed again when the parent closes. That is exactly the order the problem asks for.
Trace "(u(love)i)". The stack starts as [""]. After ( it is ["", ""]. The letter u gives ["", "u"]. Another ( gives ["", "u", ""], and love fills the top: ["", "u", "love"]. At the first ), love is popped, reversed to evol and appended to the buffer below: ["", "uevol"]. Then i gives ["", "uevoli"]. The last ) pops uevoli, reverses it to iloveu and appends it to the bottom buffer: ["iloveu"].
Step by step
- Create the stack
resas a[String]holding one empty string. The bottom buffer collects any text outside all parentheses, and it is the reason the stack is never empty while the loop runs. It is avarbecause it changes. - Loop over the characters of
s. Iterating aStringin Swift yieldsCharactervalues. - Handle
(by appending an empty string, which opens a new level. - Handle
)in anelse ifbranch with three actions, described next. - Pop the top buffer with
removeLast(), which removes the last element and returns it. This is the text inside the pair that is closing. - Reverse it.
top.reversed()produces the characters backwards, and wrapping it inString(...)turns the result back into a string. - Append it to the level below. After the pop,
res[res.count - 1]is the parent's buffer, and+=adds the reversed text to it. - Handle any other character in the
elsebranch: convert it withString(c)and append it to the top buffer. - Join and return. After the loop,
res.joined()concatenates the buffers. For balanced input only the bottom buffer is left.
The solution in Swift
class Solution {
func reverseParentheses(_ s: String) -> String {
var res: [String] = [""]
for c in s {
if c == "(" {
res.append("")
} else if c == ")" {
let top = res.removeLast()
let reversedTop = String(top.reversed())
res[res.count - 1] += reversedTop
} else {
res[res.count - 1] += String(c)
}
}
return res.joined()
}
}
Swift details worth a closer look:
reversed()does not return aString. On a string it returns aReversedCollection<String>, a lightweight view that walks the characters from the end.String(top.reversed())builds a real string from that view. The view and the string are different types, so the explicit conversion states what is stored in the buffer.CharacterversusString. The loop variablecis aCharacter. Comparing it with"("works because a double-quoted literal can be aCharacterwhen the context asks for one. Adding it to a string needsString(c).- Updating an element in place.
res[res.count - 1] += reversedTopreads the last buffer, appends and stores it back in one statement. There is no need to remove and re-add it. removeLast()returns the element. Its result is used here, which is why the call can be assigned totop. On an empty array it would crash, but balanced input guarantees there is always a buffer to pop when a)arrives, and the bottom buffer is never popped.joined()on[String]. With no argument it joins the strings with nothing between them.- Strings are values. Each
Stringin the array is copied when assigned, so reversingtopnever affects another buffer.
Complexity
Let n be the length of s.
Time: O(n²) in the worst case. Each character is appended once, but a character that sits inside d nested pairs is reversed and copied d times, once for every pair that closes around it. A string with many opening parentheses, then many letters, then the matching closing parentheses therefore does work proportional to n². With n at most 2000, that is well within the limits. For ordinary input with shallow nesting the work is close to linear.
Space: O(n). The buffers together never hold more than the letters of s, plus the temporary reversed copy.
Edge cases and common mistakes
- No parentheses.
"ab"goes straight into the bottom buffer and is returned unchanged. - Text outside the pairs.
"a(bc)d"returns"acbd": onlybcis reversed. - Pairs side by side.
"(ab)(cd)"returns"badc". Each pair is reversed on its own, and the pairs are not swapped with each other. - Nested pairs.
"((ab))"returns"ab": reversing twice restores the original order. - An empty pair.
"a()b"returns"ab". The empty buffer reverses to an empty string. - Appending to the wrong buffer. The reversed text belongs to the level below the one just popped. Appending before
removeLast()would put it into the buffer that is about to disappear. - Reversing too late. Reversing once at the very end can't produce the right result, because the innermost pairs must be reversed before their parents.
Testing
"(abcd)"gives"dcba"."(u(love)i)"gives"iloveu"."(yme(oc(da))gla)"gives"algocademy"."a(bc)d"gives"acbd"."(ab)(cd)"gives"badc".
