leetcode22. Generate Parentheses

骞讳护发布于2019-08-14 18:35 / 811人阅读

摘要：当右括号和左括号的剩余量均为时，及为一个最终结果。而则会在直接原来的对象上进行修改，其指针仍然指向原来的对象。因此在递归的过程中使用一定要注意，对对象的修改不要相互干扰。

题目要求

Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses.

For example, given n = 3, a solution set is:

[
  "((()))",
  "(()())",
  "(())()",
  "()(())",
  "()()()"
]

即生成成对的括号，其中括号的数量为n

思路和代码

这题还是一道典型的在前一种情况的前提下生成当前的情况(backtracking)。这样的题目往往需要通过递归的方式来间接记录当前的情况。
类似的题目还包括

combination sum 和 combination sum II

Permutations 和 Permutations II

我们只需要确保即将生成的结果中右括号的数量不会超过左括号即可。当右括号和左括号的剩余量均为0时，及为一个最终结果。如果左右括号的剩余量还未达到0，则将继续添加左括号或是右括号直到左右括号剩余量为0。
代码如下：

    public List generateParenthesis(int n) {
        List result = new ArrayList();
        if(n<=0){
            return result;
        }
        generateParenthesis(result, "(", n-1, n);
        return result;
        
    }
    
    private void generateParenthesis(List result, String current, int leftRemainCount, int rightRemainCount){
        if(leftRemainCount==0){
            while(rightRemainCount-->0){
                current += ")";
            }
            result.add(current);
            return;
        }
        generateParenthesis(result, current+"(", leftRemainCount-1, rightRemainCount);
        if(rightRemainCount>leftRemainCount){
            generateParenthesis(result, current+")", leftRemainCount, rightRemainCount-1);
        }
    }

利用StringBuilder简单优化

String和StringBuilder的最大区别在于，对String的任何修改都会生成一个新的String对象，并将当前的String指针指向该新生成的对象。在字符串修改频繁的场景下可能会带来大量的内存浪费。而StringBuilder则会在直接原来的对象上进行修改，其指针仍然指向原来的对象。因此在递归的过程中使用StringBuilder一定要注意，对StringBuilder对象的修改不要相互干扰。
代码如下：

    public List generateParenthesis2(int n) {
        List rst = new ArrayList<>();
        if(n == 0) {
          return rst;     
        }
        backtracking(rst, new StringBuilder(), n, n);
        return rst;
    }
    private void backtracking(List rst, StringBuilder sb, int left, int right) {
        if(left > right) {
          return;    
        }
        if(left > 0) {
          sb.append("(");
          backtracking(rst, sb, left - 1, right);
          sb.setLength(sb.length() - 1);
        }
        if(right > 0) {
          sb.append(")");
          backtracking(rst, sb, left, right - 1);
          sb.setLength(sb.length() - 1);
        }
        
        if(left == 0 && right == 0) {
          rst.add(sb.toString());  
        }
    }

想要了解更多开发技术，面试教程以及互联网公司内推，欢迎关注我的微信公众号！将会不定期的发放福利哦~

云服务器 GPU云服务器 Parentheses Generate Leetcod LeetCode

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/67100.html

LeetCode[22] Generate Parentheses

摘要：复杂度思路注意的地方，要限制左括号和右括号。每出现一次左括号，就相对于限定了，最多只能出现那么多右括号。所以，为了完成这种限定，用来控制。不然会有的情况出现。 LeetCode[22] Generate Parentheses Given n pairs of parentheses, write a function to generate all combinations of ...

Jonathan Shieber 2019-08-14 15:02 评论0 收藏0
[LeetCode] 22. Generate Parentheses

Problem Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses. For example, given n = 3, a solution set is: [ ((())), (()()), (())(), ()(()), ...

curlyCheng 2019-08-19 11:15 评论0 收藏0
leetcode 22 Generate Parentheses

摘要：要求返回一个中包含组括号所有可能的符合规则的组合。例如输入结果集应当是想法输入的就代表着我们的字符串的组成是个和个。我们需要跟踪和的使用情况，来判断下一步的操作是否合法。题目详情 Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses....

figofuture 2019-08-15 14:43 评论0 收藏0
[Leetcod] Generate Parentheses 产生括号

摘要：而对于右括号，必须前面放了一个左括号，我们才能放一个右括号。所以我们根据剩余可放置左括号，和剩余可放置右括号，代入递归，就可以求解。 Generate Parentheses 最新更新请见：https://yanjia.me/zh/2019/01/... Given n pairs of parentheses, write a function to generate all co...

Ilikewhite 2019-08-14 12:45 评论0 收藏0
leetcode 部分解答索引（持续更新～）

摘要：前言从开始写相关的博客到现在也蛮多篇了。而且当时也没有按顺序写现在翻起来觉得蛮乱的。可能大家看着也非常不方便。所以在这里做个索引嘻嘻。顺序整理更新更新更新更新更新更新更新更新更新更新更新更新更新更新更新更新前言从开始写leetcode相关的博客到现在也蛮多篇了。而且当时也没有按顺序写～现在翻起来觉得蛮乱的。可能大家看着也非常不方便。所以在这里做个索引嘻嘻。顺序整理 1~50 1...

leo108 2019-08-15 14:26 评论0 收藏0