专栏首页刷题笔记【Leet Code】22. Generate Parentheses

【Leet Code】22. Generate Parentheses

版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。

本文链接:https://blog.csdn.net/shiliang97/article/details/102000037

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:

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

来源:力扣(LeetCode) 链接:https://leetcode-cn.com/problems/generate-parentheses 著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

class Solution {
public:
    vector<string> generateParenthesis(int n) {
        dfs("",n,0);
        return result;
    }
private:
    vector<string> result;
    void dfs(string s,int left,int right)
    {
        if(left==0 && right ==0){
            result.push_back(s);
            return;
        }
        if(left>0) dfs(s+"(",left-1,right+1);
        if(right>0) dfs(s+")",left,right-1);
    }
};

传字符串,变成传字符串指针,节约了一半时间

class Solution {
public:
		vector<string> generateParenthesis(int n) {
			vector<string> result;
			string temp = "";
			dfsGP(result, temp, n, n, n);
			return result;
		}
		void dfsGP(vector<string>& result, string& cur, int n, int lN, int rN) {
			if (!lN) {
				for (int i = 0; i < rN; ++i)
					cur.push_back(')');
				result.push_back(cur);
				for (int i = 0; i < rN; ++i)
                    cur.pop_back();
			}
			else {
                cur.push_back('(');
				dfsGP(result, cur, n, lN - 1, rN);
                cur.pop_back();
				if (rN > lN) {
                    cur.push_back(')');
					dfsGP(result, cur, n, lN, rN - 1);
                    cur.pop_back();
				}
			}
		}
};

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 【HBU数据结构月考】7-2 还原二叉树 (30 分) 输出高度

    版权声明:本文为博主原创文章,遵循 CC 4.0 BY 版权协议,转载请附上原文出处链接和本声明。 ...

    韩旭051
  • 4-14 还原二叉树 (15 分)

    版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。 ...

    韩旭051
  • 【LeetCode】最长公共前缀

    版权声明:本文为博主原创文章,遵循 CC 4.0 BY 版权协议,转载请附上原文出处链接和本声明。 ...

    韩旭051
  • 非递归遍历树

    先序非递归遍历比较简单,感觉与DFS类似,根据先序遍历的规则根左右,先将根节点压入栈,然后遍历左子树,再遍历左子树的左子树,一头走到NULL,把每次遍历的左子树...

    AngelNH
  • Java游戏开发——连连看

    “连连看”是一款来源于我国台湾的桌面小游戏,主要考验的是玩家们的眼力,在有限的时间内,只要能把所有能连接的相同图案,两个两个的找出来,每找到一对,它们就会自动消...

    Java团长
  • SpringBoot 2.0 系列(三):流程详解(下)

    Spring Boot自动配置尝试根据添加的jar依赖项自动配置Spring应用程序。例如,如果 HSQLDB在我们的类路径上,并且我们没有手动配置任何数据库连...

    Vi的技术博客
  • 探索C#之6.0语法糖剖析

    蘑菇先生
  • 广告营收普遍下滑,信息流成为门户的救命稻草?

    5月17日,网易发布2018年一季度财报,财报显示电商已成为网易新的增长驱动,曾经的现金牛广告带来的净收入只有4.62亿元人民币,同比增长3.8%创下历史新低,...

    罗超频道
  • Codeforces #576 div 2 ABCD

    用户2965768
  • MySQL Table doesn’t exist in engine 解决方法

    数据表设置了外键,在phpMyAdmin中显示该表使用中,点击访问表时提示Table doesn’t exist in engine。 mysql日志显示:

    TLingC

扫码关注云+社区

领取腾讯云代金券