Generate Parentheses解题报告

Description:

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:

Example:

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

Link:

https://leetcode.com/problems/generate-parentheses/#/description

解题方法:

使两个int:leftright各表示()还剩下多少个,用递归生成字符串,过程中需遵守的规则是left 不能大于 right。并且leftright都要大于0。

Tips:

字符串可以直接用运算符'+'

helper(builder + '(', left-1, right);
helper(builder + ')', left, right-1);

Time Complexity:

O(N^2)

完整代码:

vector<string> result;
    vector<string> generateParenthesis(int n) 
    {
        int left = n, right = n;
        helper("", left, right);
        return result;
    }
    void helper(string builder, int left, int right)
    {
        if(left > right || left < 0 || right < 0)
            return;
        if(left == 0 && right == 0)
        {
            result.push_back(builder);
            return;
        }
        helper(builder + '(', left-1, right);
        helper(builder + ')', left, right-1);
    }
最后编辑于
©著作权归作者所有,转载或内容合作请联系作者
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

推荐阅读更多精彩内容

  • 背景 一年多以前我在知乎上答了有关LeetCode的问题, 分享了一些自己做题目的经验。 张土汪:刷leetcod...
    土汪阅读 12,790评论 0 33
  • 2017.11.4晴 今天叫了车,把家里的大件搬到了新家,床垫、电视柜和冰箱,叫了小弘,儿儿喜欢的小弘叔叔。中午在...
    灸灸微笑阅读 140评论 0 0
  • 2017-07-18 微信公众号零壹圈 不知什么时候开始,流行这样一句话,你的层次由身边的朋友决定。这话流行开来,...
    一飞5阅读 589评论 0 1
  • 2017年4月21日 相濡以沫 1、开始给自己规划三件当天最重要的事,做一件让自己感觉幸福的事,晚上回顾完成了哪些...
    滋滋味味阅读 346评论 5 2
  • 网站是企业在互联网上与用户沟通的主要渠道,网站的完美程度将对用户对于企业的第一印象产生极大的影响。那么企业建设网站...
    perdarq阅读 1,015评论 1 1