LeetCode生成匹配的括号

剑指 Offer II 085. 生成匹配的括号

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

输入：n = 3
输出：[“((()))”,“(()())”,“(())()”,“()(())”,“()()()”]

来源：LeetCode

回溯法。
左括号的个数记为left，右括号个数为right，而结果中左右括号个数一定是n个，也就是说括号数最大为n；
新建StringBuilder类的对象cur用来存储当前有可能构成最终结果的情况；
res集合存储最终返回的结果。

回溯的条件就是当cur中的左括号和右括号个数都是n的时候，此时也要将cur这种情况加入到res中。

以下代码是在加入cur的元素是最终的情况下考虑的，所以一定要保证左括号比n小时才会添加左括号，并且当右括号个数小于左括号时才会添加右括号。

而在每次返回也就是回溯时，要考虑不添加的情况，所以要删除该节点添加进cur的元素，也就是删除cur中最后一个元素。

最终将所有情况均加入进res中，返回res即可。

class Solution {
    public List<String> generateParenthesis(int n) {
        List<String> res = new ArrayList<String>();
        
        trackback(res,n,0,0,new StringBuilder());
        return res;
    }

    public void trackback(List<String> res,int max,int left,int right,StringBuilder cur){
        if(max*2==cur.length()){
            res.add(cur.toString());
            return;
        }
        if(left<max){
            cur.append("(");
            trackback(res,max,left+1,right,cur);
            cur.deleteCharAt(cur.length()-1);
            
        }
        if(right<left){
            cur.append(")");
            trackback(res,max,left,right+1,cur);
            cur.deleteCharAt(cur.length()-1);
        }
    }

}
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

StringBuffer和StringBuilder：
两者都继承自AbstractStringBuilder类
区别：
1.StringBuffer 的所有公开方法都是 synchronized 修饰的，所以StringBuffer线程安全，StringBuilder线程不安全。
2.StringBuffer 每次获取 toString 都会直接使用缓存区的 toStringCache 值来构造一个字符串。而 StringBuilder 则每次都需要复制一次字符数组，再构造一个字符串。
3.StringBuilder没有对方法加锁同步，StringBuilder性能大于StringBuffer。
StringBuffer适用于多线程，Stringbuilder适合单线程。

参考博文

String、StringBuffer和StringBuilder底层都是通过char数组来实现的；
String对象一旦创建，值不能更改，如果修改值需要开辟新的内存空间存储修改后的对象，StringBuffer和StringBuilder对象的值是可以被修改的。