Skip to content

1190. Reverse Substrings Between Each Pair of Parentheses 👍

Approach 1: Brute Force

  • Time: $O(n^2)$
  • Space: $O(n)$
 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<int> stack;
    string ans;

    for (const char c : s)
      if (c == '(') {
        stack.push(ans.length());
      } else if (c == ')') {
        // Reverse the corresponding substring between ().
        const int j = stack.top();
        stack.pop();
        reverse(ans.begin() + j, ans.end());
      } else {
        ans += c;
      }

    return ans;
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
  public String reverseParentheses(String s) {
    Deque<Integer> stack = new ArrayDeque<>();
    StringBuilder sb = new StringBuilder();

    for (final char c : s.toCharArray())
      if (c == '(') {
        stack.push(sb.length());
      } else if (c == ')') {
        // Reverse the corresponding substring between ().
        StringBuilder reversed = new StringBuilder();
        for (int sz = sb.length() - stack.pop(); sz > 0; --sz) {
          reversed.append(sb.charAt(sb.length() - 1));
          sb.deleteCharAt(sb.length() - 1);
        }
        sb.append(reversed);
      } else {
        sb.append(c);
      }

    return sb.toString();
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
class Solution:
  def reverseParentheses(self, s: str) -> str:
    stack = []
    ans = []

    for c in s:
      if c == '(':
        stack.append(len(ans))
      elif c == ')':
        # Reverse the corresponding substring between ().
        j = stack.pop()
        ans[j:] = ans[j:][::-1]
      else:
        ans.append(c)

    return ''.join(ans)

Approach 2: $O(n)$

  • Time: $O(n)$
  • Space: $O(n)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class Solution {
 public:
  string reverseParentheses(string s) {
    string ans;
    stack<int> stack;
    unordered_map<int, int> pair;

    for (int i = 0; i < s.length(); ++i)
      if (s[i] == '(') {
        stack.push(i);
      } else if (s[i] == ')') {
        const int j = stack.top();
        stack.pop();
        pair[i] = j;
        pair[j] = i;
      }

    for (int i = 0, d = 1; i < s.length(); i += d)
      if (s[i] == '(' || s[i] == ')') {
        i = pair[i];
        d = -d;
      } else {
        ans += s[i];
      }

    return ans;
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution {
  public String reverseParentheses(String s) {
    StringBuilder sb = new StringBuilder();
    Deque<Integer> stack = new ArrayDeque<>();
    Map<Integer, Integer> pair = new HashMap<>();

    for (int i = 0; i < s.length(); ++i)
      if (s.charAt(i) == '(') {
        stack.push(i);
      } else if (s.charAt(i) == ')') {
        final int j = stack.pop();
        pair.put(i, j);
        pair.put(j, i);
      }

    for (int i = 0, d = 1; i < s.length(); i += d)
      if (s.charAt(i) == '(' || s.charAt(i) == ')') {
        i = pair.get(i);
        d = -d;
      } else {
        sb.append(s.charAt(i));
      }

    return sb.toString();
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution:
  def reverseParentheses(self, s: str) -> str:
    ans = []
    stack = []
    pair = {}

    for i, c in enumerate(s):
      if c == '(':
        stack.append(i)
      elif c == ')':
        j = stack.pop()
        pair[i] = j
        pair[j] = i

    i = 0
    d = 1
    while i < len(s):
      if s[i] in '()':
        i = pair[i]
        d = -d
      else:
        ans.append(s[i])
      i += d

    return ''.join(ans)