leetcode22. 括号生成

leetcode22. 括号生成

四月 11, 2020

leetcode22. 括号生成

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

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

递归的题刷的多了，这题刚读完，就来灵感了。
第一个必须是 ( 。然后下一个加什么括号取决于左边括号有几个，右边有几个。

  • 如果左边括号的数量小于n，那么可以加 ( 。
  • 如果左边括号数量大于右边括号，呢么可以加 ) 。
  • 终止条件是左括号数量等于右括号数量并且都为n。
    由于只有一种括号， ( 一定能找到 ) 。也就是说( [ ) ] 的情况不会出现。也可能是我想多了。
    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
     class Solution {
        public List<String> generateParenthesis(int n) {
            if (n == 0) {
                list.add("");
                return list;
            }
            build(new StringBuilder("("), 1, 0, n);
            return list;
        }
        private LinkedList<String> list = new LinkedList<>();
        public void build(StringBuilder sb, int left, int right, int n) {
            if (left == right && left == n) {
                //System.out.println("over is "+sb);
                list.add(new String(sb));
                return ;
            }
            //直接append的话，left是递归之后的结果，比如((())),
            //这样下面的right就会用到((())),而不是想要的状态
            //replace也是同样的道理，我们想只replace最后一个，但是实际上这个字符串已经和最开始差很多了
            //不明白的就实践一下
            StringBuilder lefts = new StringBuilder(sb);
            StringBuilder rights = new StringBuilder(sb);
            lefts.append("(");
            if (left < n) {
                build(lefts, left + 1, right, n);
            }

            rights.append(")");
            if (left > right) {
                build(rights, left, right + 1, n);
            }
        }
    }
    leetcode 74/100