This article is participating in the “Java Theme Month – Java Brush questions punch card”, see the activity link for details

Fundamental analysis

According to the problem, we can design the following processing flow:

  • Traversing the string backwards and forwards will not)The string from the “tail” is put into the queue
  • When faced with)The string is fetched from the “tail” of the queue until encountered(And flip the retrieved string
  • The flipped string is put back into the queue from the “tail”
  • Repeat the above process until the original string is complete
  • Take characters from the “head” of the queue to get the final answer

As you can see, the above process requires the use of a double-endian queue (or stack, which in the case of the stack requires another flip at the last step to retrieve the string).

In Java, a two-endian queue can use its own ArrayDeque, or it can be emulated directly using arrays.

The language comes with a dual-endian queue

Code:

class Solution {
    public String reverseParentheses(String s) {
        int n = s.length();
        char[] cs = s.toCharArray();
        Deque<Character> d = new ArrayDeque<>();
        for (int i = 0; i < n; i++) {
            char c = cs[i];
            if (c == ') ') {
                StringBuilder path = new StringBuilder();
                while(! d.isEmpty()) {if(d.peekLast() ! ='(') {
                        path.append(d.pollLast());
                    } else {
                        d.pollLast();
                        for (int j = 0; j < path.length(); j++) {
                            d.addLast(path.charAt(j));
                        }
                        break; }}}else {
                d.addLast(c);
            }
        }
        StringBuilder sb = new StringBuilder();
        while(! d.isEmpty()) sb.append(d.pollFirst());returnsb.toString(); }}Copy the code
  • Time complexity: each(Characters enter and exit the queue only once;)Strings don’t go in or out of the queue and are scanned only once; The analysis focuses on ordinary characters, and you can see that the number of times each ordinary character enters and exits the queue depends on the number to its right)In the worst case, every character has close parentheses to the right, so the complexity can be used as
    O ( n 2 ) O(n^2)
  • Space complexity: O(n)O(n)O(n)

Array simulates a two-ended queue

Code:

class Solution {
    char[] deque = new char[2009];
    int head = 0, tail = -1;
    char[] path = new char[2009];
    public String reverseParentheses(String s) {
        int n = s.length();
        char[] cs = s.toCharArray();
        for (int i = 0; i < n; i++) {
            char c = cs[i];
            if (c == ') ') {
                int idx = 0;
                while (tail >= head) {
                    if (deque[tail] == '(') {
                        tail--;
                        for (int j = 0; j < idx; j++) {
                            deque[++tail] = path[j];
                        }
                        break;
                    } else{ path[idx++] = deque[tail--]; }}}else {
                deque[++tail] = c;
            }
        }
        StringBuilder sb = new StringBuilder();
        while (tail >= head) sb.append(deque[head++]);
        returnsb.toString(); }}Copy the code
  • Time complexity: each(Characters enter and exit the queue only once;)Strings don’t go in or out of the queue and are scanned only once; The analysis focuses on ordinary characters, and you can see that the number of times each ordinary character enters and exits the queue depends on the number to its right)In the worst case, every character has close parentheses to the right, so the complexity can be used as
    O ( n 2 ) O(n^2)
  • Space complexity: O(n)O(n)O(n)