首页 > 代码库 > leetcode--Generate Parentheses

leetcode--Generate Parentheses

2024-07-07 07:38:48   224人阅读

Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses.

For example, given n = 3, a solution set is:

"((()))", "(()())", "(())()", "()(())", "()()()"

?
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
41
42
43
44
45
46
public class Solution {
    /**In order to generate valid parenthesis, the number of
     * "(" should not smaller than the number of ")". So, we use a List<Integer>
     * to save the number of "(". So the number of ")" can be calculated.
     * @param n --Integer, number of parentheses
     * @return List of valid parentheses strings
     * @author Averill Zheng
     * @version 2014-06-04
     * @since JDK 1.7
     */
    public List<String> generateParenthesis(int n) {
        List<String> validParen = new ArrayList<String>();
        List<Integer> numberOfLeftParen = new ArrayList<Integer>();
        if(n > 0){
            validParen.add("(");
            numberOfLeftParen.add(1);
            for(int i = 2; i <= 2*n; ++i){
                List<String> tempValidParen = new ArrayList<String>();
                List<Integer> num = new ArrayList<Integer>();
                int length = validParen.size();
                for(int j = 0; j < length; ++j){
                    //the length of string in list now is i - 1
                    int leftParen = numberOfLeftParen.get(j); // it implies that number of ")" is i - 1 - leftParen                
                    String s = validParen.get(j);
                    if(leftParen == n){
                        tempValidParen.add(s + ")");
                        num.add(leftParen);
                    }
                    else if(leftParen <= (i - 1 - leftParen)){
                        tempValidParen.add(s + "(");
                        num.add(leftParen + 1);
                    }
                    else{
                        tempValidParen.add(s + "(");
                        num.add(leftParen + 1);
                        tempValidParen.add(s + ")");
                        num.add(leftParen);
                    }
                }
                validParen = tempValidParen;
                numberOfLeftParen = num;
            }
        }
        return validParen;
    }
}

　　


联系
我们