22.括号生成

发表于： 2023-10-07 分类于： leetcode

字数： 1150 阅读：≈ 3分钟

🏧 22.括号生成

数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且 有效的 括号组合。

思路

基本思想

为了找出所有的合法括号组合,最简单的办法就是找出所有的括号组合,然后从中筛选出合法的括号组合,这个方法分为两步:

产生出所有的括号组合

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
public void generate(char[] path,int pos){
    //括号组合生成完成，数组填充满了
    if(path.length==pos){
        if(isValid(path))
            res.add(new String(path));
        return;
    }
    else{
        //对于当前位置,要么添加(,要么添加),形成2*n的长度立即返回
        //可以递归搜索出所有的结果
        //两种递归方式，因为每个位置有两种填充方式（左括号或者）
        path[pos]='(';
        generate(path,pos+1);
        path[pos]=')';
        generate(path,pos+1);
    }
}

给定三个括号,一共六个位置,每个位置不是放置左括号就是放置右括号,所以可以使用递归的方法产生出所有的括号组合

判断括号组合是否合法

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
public boolean isValid(char[] path){
    int balance = 0;
    for (char c: path) {
        if (c == '(') {
            ++balance;
        } else {
            --balance;
        }
        if (balance < 0) {
            return false;
        }
    }
    return balance == 0;
}

统计出所有的左括号数量,遇到一个右括号就将左括号的数量-1,当左括号的数量小于零时,括号组合不合法,返回false,当统计结束左括号还有剩余,也返回false,除此之外返回true

以上方法亲测可行,但是还可以进一步改进

上面的方法每次添加新括号时,可以进一步筛选,只有当右括号的数量大于等于左括号的数量时,才能继续添加一个右括号,否则右边的括号就不能无脑添加

左括号的数量超过整体数量的一半时,左括号也不能添加,所以可以添加了两个变量,记录左右括号的数量,简单的添加两个变量之后,可以减小很多搜索过程,一旦在途中数量不符合要求,就已经提前结束了

执行流程

递归生成所有括号的组合,每一个位置要么添加左括号,要么添加右括号
对于每个位置来说,左括号的数量不能超过总数的一半,右括号的数量不能超过左括号
每生成一种括号的组合,都判断其是否合法
合法的括号加入结果容器中
返回结果

代码

根据以上分析,得出以下代码:

 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
47
48
class Solution {
    List<String> res=new ArrayList<>();
    //利用递归产生出所有的括号组合,之后找出合法的括号组合
    public List<String> generateParenthesis(int n) {
        char[] path=new char[2*n];
        generate(path,0,0,0,n);
        return res;
    }
    //递归产生所有括号组合
    public void generate(char[] path,int pos,int left,int right,int n){
        if(path.length==pos){
            if(isValid(path))
                res.add(new String(path));
            return;
        }
        else{
            //对于当前位置,要么添加(,要么添加),形成2*n的长度立即返回
            //可以递归搜索出所有的结果
            //左括号的数量不能超过总数的一半
            if(left<n){
                path[pos]='(';
                generate(path,pos+1,left+1,right,n);
            }
            //右括号的数量不能超过左括号
            if(right<left){
                path[pos]=')';
                generate(path,pos+1,left,right+1,n);
            }
        }
    }
    public boolean isValid(char[] path){
        int balance = 0;
        for (char c: path) {
            //统计左括号的数量
            if (c == '(') {
                ++balance;
            } else {//遇到右括号就与左括号抵消
                --balance;
            }
            //左括号不够抵消返回false
            if (balance < 0) {
                return false;
            }
        }
        //左括号有冗余也返回false
        return balance == 0;
    }
}

总结

思想很简单,主要是代码模拟能力,使用递归将所有的括号组合都生成出来,在生成的过程中加上控制条件,生成结束再进行过滤,一层一层的筛选,减小搜索开销的同时得到正确答案