【LeetCode - Java】22. 括号生成（中等）

1. 题目描述2. 解题思路3. 代码实现

3.1 DFS回溯3.2 小改进+对比

简单的中等题喜加一！当然前提是你已经做过了【LeetCode - Java】17. 电话号码的字母组合（中等）这道题，两道题的本质思想还是一样的，生成符合规则的字符串，而我个人认为这道题比那道题更进一步，多了一个规则判断（是否合规括号）。

借鉴DFS的思想，我们这道题可以利用StringBuilder进行回溯生成目标字符串。要注意的地方只有一个：合规括号在数理上如何表示呢？根据我们的经验不难发现，在有效括号中任意位置截断，前半部分的左括号数量总是大于等于右括号数量的，那么我们就可以利用这一点在生成括号的过程中控制右括号是否可以加入字符串中。那左括号呢？没有限制，只要不超过限定值都可以把他加进去。

private final linkedList list = new linkedList<>();
    private final StringBuilder sb = new StringBuilder("(");
    private int left_count = 1, right_count = 0;

    @Override
    public List generateParenthesis(int n) {
        buildString(1, n);
        return list;
    }

    public void buildString(int index, int n) {
        if (index == 2 * n) {
            list.add(sb.toString());
            return;
        }
        if (right_count < left_count) {
            right_count++;
            sb.append(")");
            buildString(index + 1, n);
            sb.deleteCharAt(index);
            right_count--;
        }
        if (left_count < n) {
            left_count++;
            sb.append("(");
            buildString(index + 1, n);
            sb.deleteCharAt(index);
            left_count--;
        }
    }

上述想法在实现的过程中返回的List我是使用了linkedList进行构造的，为什么不选用ArrayList呢？最初想法是ArrayList的底层是由数组实现，增加或删除元素需要进行数组的新建复制，可能会影响时间与空间表现，因此选用了底层实现为链表的linkedList。结果发现linkedList的时间没有达到最优的表现，出于好奇试了一下ArrayList，fine，竟然表现更好了，颠覆了我的认知判断！有知道为啥的大佬可以在评论区留下你们的看法。

private final ArrayList list = new ArrayList<>();

话说回来，时间复杂度是多少呢？这道题目的迭代与循环都是为了生成字符串，时间复杂度的计算是与生成字符串的数量挂钩的，这里涉及相对复杂的计算证明（我也搞不出来），官解所表示的时间复杂度为O( 4 n / n 4^n/sqrt{n} 4n/n ​)。

对于空间复杂度就好分析多了，主要的额外空间消耗是递归迭代所需要的栈的深度，显然深度为2n，因此空间复杂度为O(n)。