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.

Example 4:
Input: s = “a(bcdefghijkl(mno)p)q”
Output: “apmnolkjihgfedcbq”

Constraints:
0 <= s.length <= 2000
s only contains lower case English characters and parentheses.
It’s guaranteed that all parentheses are balanced.

Hints:
Find all brackets in the string.
Does the order of the reverse matter?
The order does not matter.

Using Stack to Keep Tracking the Level of Parentheses

We can use a stack to keep tracking the Parentheses. Also, we can use a variable to record the current string in the current level. If we meet open bracket, we push the current string to the stack, reseting it to “”. And we meet an close bracket, we need to reverse the current string, and add it to the top element of the stack.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

class Solution {
public:
    string reverseParentheses(string s) {
        stack<string> st;
        string cur = "";
        for (int i = 0; i < s.size(); ++ i) {            
            if (s[i] == '(') {
                st.push(cur);
                cur = "";
            } else if (s[i] == ')') {
                std::reverse(begin(cur), end(cur));
                string s = st.top();
                st.pop();
                cur = s + cur;
            } else {
                cur += s[i];
            }
        }
        return cur;
    }
};

class Solution {
public:
    string reverseParentheses(string s) {
        stack<string> st;
        string cur = "";
        for (int i = 0; i < s.size(); ++ i) {            
            if (s[i] == '(') {
                st.push(cur);
                cur = "";
            } else if (s[i] == ')') {
                std::reverse(begin(cur), end(cur));
                string s = st.top();
                st.pop();
                cur = s + cur;
            } else {
                cur += s[i];
            }
        }
        return cur;
    }
};

The complexity is O(N) and the space complexity is also O(N). The stack implements a First In Last Out, and hence is often used in the Parentheses problems.

The std::reverse() is perfect to reverse a string, substring, or a vector.

–EOF (The Ultimate Computing & Technology Blog) —