[Leetcod] Generate Parentheses 产生括号

Ilikewhite 发布于2019-08-14 12:45 / 1751人阅读

摘要：而对于右括号，必须前面放了一个左括号，我们才能放一个右括号。所以我们根据剩余可放置左括号，和剩余可放置右括号，代入递归，就可以求解。

Generate Parentheses 最新更新请见：https://yanjia.me/zh/2019/01/...

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:
"((()))", "(()())", "(())()", "()(())", "()()()"

回溯法 复杂度

时间 O(N) 空间 O(N) 递归栈

思路

当我们放置一个新的符号时，我们有两个选择，放置左括号，或者放置右括号，但是按照题意我们最多放置n个左括号，放一个剩余可放置左括号就少一个，但剩余可放置右括号则多了一个。而对于右括号，必须前面放了一个左括号，我们才能放一个右括号。所以我们根据剩余可放置左括号，和剩余可放置右括号，代入递归，就可以求解。

代码

public class Solution {
    
    List res = new LinkedList();
    
    public List generateParenthesis(int n) {
        helper(n, 0, "");
        return res;
    }
    
    private void helper(int left, int right, String tmp){
        // 如果左括号右括号都放完了，则找到一个结果
        if(left == 0 && right == 0){
            res.add(tmp);
            return;
        }
        // 对于每个位置，我们有两种选择，要么放左括号，要么放右括号
        if (left > 0){
            helper(left - 1, right + 1, tmp+"(");
        }
        if (right > 0){
            helper(left, right - 1, tmp+")");
        }
    }
}

后续 Follow Up

Q:如果想把生成的括号加上缩进来格式化怎么办？
A:将原先if(left == 00 && right == 0)里面替换为：

int level = 0;
for(int i = 0; i < tmp.length(); i++){
    if(tmp.charAt(i) == "{"){
        for(int k = 0; k < level; k++){
            System.out.print("	");
        }
        System.out.println("{");
        level++;
    } else {
        level--;
        for(int k = 0; k < level; k++){
            System.out.print("	");
        }
        System.out.println("}");
    }
}

混合云专线服务 Leetcod Parentheses Generate 云计算产生

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

转载请注明本文地址：https://www.ucloud.cn/yun/64685.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
leetcode22. Generate Parentheses

摘要：当右括号和左括号的剩余量均为时，及为一个最终结果。而则会在直接原来的对象上进行修改，其指针仍然指向原来的对象。因此在递归的过程中使用一定要注意，对对象的修改不要相互干扰。题目要求 Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses....

骞讳护 2019-08-14 18:35 评论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
构造n个成对括号

摘要：构造个成对括号给出一个整数，实现一个函数生成对小括号，对小括号的左右括弧顺序不限，但应该闭合。思路的情况为时的括号串中在缝隙位置再插入一个括号，如中位置。递归解决，时为在和中再插入一个括号。构造n个成对括号 Generate Parentheses 给出一个整数n，实现一个函数生成n对小括号，n对小括号的左右括弧顺序不限，但应该闭合。 Given n pairs of parent...

姘搁『 2019-07-30 14:20 评论0 收藏0
leetcode 301. Remove Invalid Parentheses

摘要：一个合法的字符串是指左括号和右括号必定成对出现。要求得出用最少次数的删除可以得到的所有的合法字符串。最后两个结果重复，因此只保留，两个结果。最终生成的合法字符串为。方法相同于上一种情况。其中出现了两次。在该下标前的删除将会产生重复的结果。题目要求 Remove the minimum number of invalid parentheses in order to make the...

zhisheng 2019-08-15 14:41 评论0 收藏0