leetcode 22 Generate Parentheses

figofuture 发布于2019-08-15 14:43 / 1997人阅读

摘要：要求返回一个中包含组括号所有可能的符合规则的组合。例如输入结果集应当是想法输入的就代表着我们的字符串的组成是个和个。我们需要跟踪和的使用情况，来判断下一步的操作是否合法。

题目详情

Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses.输入一个正整数n。要求返回一个List,list中包含n组括号所有可能的符合规则的组合。如“（（））”就属于符合规则的组合，“)(()”就属于不符合规则的组合。
例如, 输入 n = 3, 结果集应当是:
[
  "((()))",
  "(()())",
  "(())()",
  "()(())",
  "()()()"
]

想法

输入的n就代表着我们的字符串的组成是n个"("和n个")"。

声明一个cur字符串来暂存我们没次操作获得的字符串，而我们每次想要将括号加入cur字符串的时候，我们要保证剩余的括号和现有字符串，可以满足规则。也就是说，如果我们想加入一个")"，我们要保证cur字符串中的")"的数量小于"("的数量，否则字符串就不符合规则了。

我们需要跟踪"("和")"的使用情况，来判断下一步的操作是否合法。

解法

     public List generateParenthesis(int n) {
            List ans = new ArrayList();
            backtrack(ans, "", 0, 0, n);
            return ans;
        }

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

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

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

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

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