/ Data Structure and Algorithms  

Leetcode 22. Generate Parentheses

Question



Give a number n and return all valid parenthetical matches, exactly the opposite of 20. Valid Parentheses.

Similar Questions

Soultion - Brute Force

Enumerate all cases, each of which has left and right parenthesis, a total of 2n digits, so a total of 22n cases.

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
29
30
31
32
33
34
35
36
37
38
39
40
public List<String> generateParenthesis(int n) {
    List<String> results = new ArrayList<>();

    generateAll(results, new char[n * 2], 0);

    return results;
}

private void generateAll(List<String> result, char[] current, int pos) {
    if (pos == current.length) {
        if (isValid(current)) {
            result.add(new String(current));
        }
    } else {
        // if n-th digit is '('
        current[pos] = '(';
        generateAll(result, current, pos + 1);
        current[pos] = ')';
        // if n-th digit is ')'
        generateAll(result, current, pos + 1);
    }
}

private boolean isValid(char[] current) {
    int balance = 0;

    for (char c : current) {
        if (c == '(') {
            balance++;
        } else {
            balance--;
        }

        if (balance < 0) {
            return false;
        }
    }

    return balance == 0;
}

Time complexity: O(n) is needed to judge whether each case is legal, so the time complexity is O(22nn)

Space complexity: O(22nn), multiply by n because the length of each string is 2n. In addition, this is assuming that all conditions are met, but it is not possible to meet all of them, and more accurate situations will be given later.

Solution

In previous solution, we keep adding left parentheses. In fact, if the left parenthesis exceeds n, it is definitely not a legal case. Because the legal case must be n left parentheses and n right parentheses.

Another case is that if the total number of right parentheses is greater than the total number of left parentheses in the process of adding parentheses, no matter what is added later, it cannot be a legal case. Because each right parenthesis must match a previous left parenthesis, if there are more right parentheses than left parentheses, then there must be a right parenthesis that does not match the left parenthesis, no matter how many left parentheses are added later, it is useless. For example, n = 3, there will be 6 parentheses in total. When we add ()) to 3 parentheses, there are 1 left parenthesis and 2 right parentheses. At this moment, the 3 parentheses behind it are doomed. Will not be a legal case anymore.

Based on the two points above, as long as we avoid them, we can guarantee that the brackets we generate must be legal.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
public List<String> generateParenthesis(int n) {
    List<String> results = new ArrayList<>();

    generateAll(results, "", 0, 0, n);

    return results;
}

private void generateAll(List<String> result, String current, int left, int right, int n) {
    if (current.length() == n * 2) {
        result.add(current);
    } else {
        // add left '(' as many as possible
        if (left < n) {
            generateAll(result, current + "(", left + 1, right, n);
        }

        // add right ')'
        if (right < left) {
            generateAll(result, current + ")", left, right + 1, n);
        }
    }
}

The execution order of the recursion as follows:

1
2
3
4
5
6
7
8
9
( -> (( -> ((( -> ((() -> ((()) -> ((())) -> add to result

(( -> (() -> (()( -> (()() -> (()()) -> add to result

(( -> (() -> (()) -> (())( -> (())() -> add to result

( -> () -> ()( -> ()(( -> ()(() -> ()(()) -> add to result

( -> () -> ()( -> ()() -> ()()( -> ()()() -> add to result