LeetCode[22] Generate Parentheses

Jonathan Shieber 发布于2019-08-14 15:02 / 3406人阅读

摘要：复杂度思路注意的地方，要限制左括号和右括号。每出现一次左括号，就相对于限定了，最多只能出现那么多右括号。所以，为了完成这种限定，用来控制。不然会有的情况出现。

LeetCode[22] Generate Parentheses

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

BackTracking

复杂度
O(N!),O(N)

思路
注意trick的地方，要限制左括号和右括号。每出现一次左括号，就相对于限定了，最多只能出现那么多右括号。所以，为了完成这种限定，用right - 1来控制。不然会有“(()))(”的情况出现。

代码

public List generateParenthesis(int n) {
    List res = new LinkedList<>();
    helper(res, 0, n, n, new StringBuilder());
    return res;
}

public void helper(List res, int left, int right, int n, StringBuilder temp) {
    // Base case;
    if(left == n && right == n) {
        res.add(temp.roString());
    }
    if(left < n) {
        // 限制在当前这么多左括号的情况下，最多只能出现那么多的右括号。
        helper(res, left + 1, right - 1, n, temp.append("("));
        temp.deleteCharAt(temp.length() - 1);
    }
    if(right < n) {
        helper(res, left, right + 1, n, temp.append(")"));
        temp.deleteCharAt(temp.length() - 1);
    }
}

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

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

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

[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
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
leetcode 部分解答索引（持续更新～）

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

leo108 2019-08-15 14:26 评论0 收藏0
构造n个成对括号

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

姘搁『 2019-07-30 14:20 评论0 收藏0