421. Unwrap the Brackets
A message was scrambled by a machine that works on bracket groups. Whenever the machine meets a pair of matching brackets, it reverses the text between them, and then removes the pair of brackets. Groups may be nested; the innermost groups are reversed first, and the reversal of an outer group then includes the already reversed inner text.
Given the scrambled string s, made of lower-case letters and balanced round brackets, return the final text with all brackets removed. Doing the reversals one group at a time is too slow for deeply nested input; aim for a linear solution.
Example 1
- Input:
- s = "ab(cde)f"
- Output:
- "abedcf"
- Explanation:
The group (cde) is reversed to edc and its brackets disappear, giving abedcf.
Example 2
- Input:
- s = "(x(yz)w)q"
- Output:
- "wyzxq"
- Explanation:
The inner (yz) becomes zy, so the outer group holds xzyw. Reversing it gives wyzx, followed by q.
Constraints
1 ≤ s.length ≤ 20000s contains only lower-case English letters and the characters '(' and ')'.
The brackets in s are balanced.
How this problem is judged
- Answers
- Your answer must match exactly. Numbers compare by value, so 2 and 2.0 are equal.
- Time per case
- Python 400 msC++ 100 msJava 200 msJavaScript 200 msTypeScript 200 ms
Expected complexity
- Time
- O(n)
- Space
- O(n)