乘风破浪:LeetCode真题_022_Generate Parentheses

时间:2022-12-29 14:04:34

乘风破浪:LeetCode真题_022_Generate Parentheses

一、前言

   关于括号的题目,我们已经遇到过了验证正确性的题目,现在让我们生成合法的括号列表,怎么办呢?想来想去还是递归比较方便。

二、Generate Parentheses

2.1 问题

乘风破浪:LeetCode真题_022_Generate Parentheses

2.2 分析与解决

    既然用递归就要构造模型,这里我们定义left和right分别代表剩余的左右括号的数目,如果出现了left>right,那么就会出现实际上的左括号小于右括号的结果,出现错误,如果剩余都小于零就结束,只有都剩余为0的时候才记录,这样我们就得到了结果。

public class Solution {
    public List<String> generateParenthesis(int n) {
        List<String> res = new ArrayList<String>();
        helper(n, n, "", res);
        return res;
    }
    void helper(int left, int right, String out, List<String> res) {
        if (left < 0 || right < 0 || left > right) return;
        if (left == 0 && right == 0) {
            res.add(out);
            return;
        }
        helper(left - 1, right, out + "(", res);
        helper(left, right - 1, out + ")", res);
    }
}

 乘风破浪:LeetCode真题_022_Generate Parentheses

    那么官方是怎么说的呢?

乘风破浪:LeetCode真题_022_Generate Parentheses

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) {
        if (pos == current.length) {
            if (valid(current))
                result.add(new String(current));
        } 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);
    }
}

     也是用了一种递归的方法,先生成左括号,再递归,直至遍历完所有的情况,因此复杂度非常的高,究其原因是没有考虑到一些本来就可以省略的情况。

 乘风破浪:LeetCode真题_022_Generate Parentheses

    于是做出了改进,将一些情况进行了优化,只有右括号小于左括号的时候才能添加右括号,左括号也不能超过最大的上限:

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

    public void backtrack(List<String> ans, String cur, int open, int close, int max){
        if (cur.length() == max * 2) {
            ans.add(cur);
            return;
        }

        if (open < max)
            backtrack(ans, cur+"(", open+1, close, max);
        if (close < open)
            backtrack(ans, cur+")", open, close+1, max);
    }
}

三、总结

    这一题其实是比较难的,因为我们可能无从下手,就算用递归的时候也不能抓住要害,因此如何定义递归中变量的含义至关重要。