LeetCode Notes_#22_括号生成

LeetCode

Contents

题目
解答
方法1:暴力递归
复杂度分析
方法2：回溯
复杂度分析

题目

解答

方法1:暴力递归

给出括号对数n之后，就确定了括号组合的字符串长度必然是2n，我们可以通过暴力递归的方式，在2n个位置上放置'('或者')',得到所有的排列序列，然后逐个判断每个排列序列是否是正确的，将正确的排列序列加入到结果列表当中。

class Solution {
    public List<String> generateParenthesis(int n) {
        List<String> combinations = new ArrayList<>();
        generateAll(new char[2*n], 0, combinations);
        return combinations;
    }
    
    public void generateAll(char[] current, int pos, List<String> result){
        //出口条件：pos指针指向current的末尾之后一个位置（末尾是current.length - 1）
        if(pos == current.length){
            if(valid(current)){
                result.add(new String(current));
            }
        //递推过程：在current数组末尾位置添加'('或者')',然后进行递归调用，在下一个位置pos + 1继续添加'('或者')'
        //这个过程中并不考虑'('和')'之间的数量以及配对是否是正确的，而是在将整个字符串都生成后，才判断这个字符串是否是正确配对的
        }else{
            current[pos] = '(';
            generateAll(current, pos + 1, result);
            current[pos] = ')';
            generateAll(current, pos + 1, result);
        }
    }
    //验证一个排列序列是否正确
    public boolean valid(char[] current){
        int balance = 0;
        for(char c: current){
            if(c == '('){
                balance++;
            }else{
                balance--;
            }
            if(balance < 0){
                return false;
            }
        }
        return balance == 0;
    }
}

复杂度分析

时间复杂度：,排列序列一共有个，对于每个排列序列，调用valid()方法进行验证，其时间复杂度为。
空间复杂度：,递归栈的深度是2n层。

方法2：回溯

在暴力递归法当中，我们其实生成了很多无效的排列序列，但是都要等到最后才能判断出它们是无效的。更优的方法应该是在构造序列的时候，就进行剪枝，对于已经确认无效的序列，提前将其排除（剪枝）。
回溯法里边的回溯，指的就是撤销选择这一过程，无论这一次选择的结果是不是正确的，我们都需要回溯回去，尝试其他的可能性。

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

    // left,right代表左括号，右括号出现的次数
    private void backtrack(List<String> ans, StringBuilder cur, int left, int right, int n){
        //出口条件：长度达到2n,可以保证结果是正确的，直接加入结果列表当中
        if(cur.length() == 2*n){
            ans.add(cur.toString());
            return;
        }
        //左括号数量<n,可以继续添加左括号
        if(left < n){
            cur.append('(');
            backtrack(ans, cur, left + 1, right, n);
            cur.deleteCharAt(cur.length() - 1);
        }
        //右括号的数量<左括号的数量，可以继续添加右括号
        if(right < left){
            cur.append(')');
            backtrack(ans, cur, left, right + 1, n);
            cur.deleteCharAt(cur.length() - 1);
        }
    }
}