【leetcode】Generate Parentheses

题目:

给定整数n,返回n对匹配的小括号字符串数组。

For example, given n = 3, a solution set is:

"((()))", "(()())", "(())()", "()(())", "()()()"

分析:

这种问题的模式是:1)问题的解有多个 ,2)每个解都是由多个有效的 ”步骤“ 组成的,3)变更以有解的某个或某些”步骤“ 可以形成新的解。这类问题差不多用dfs都能得到解决。

看看这个题目,括号只有两种 “("  ,")" ,初始第一个必须为"("。如果我们把初始的左括号视为二叉树的根节点,满足插入"("的条件我们就构建左子树,满足插入”)“的条件我们就构建右子树。

以N = 3为例,我们手动画下来所有的匹配组成就是这个。合法的括号匹配序列应该满足卡塔兰数性质。

那么这个问题就是深度遍历二叉树的过程了。与二叉树遍历不同的是访问左右子树时的判断条件,就是从根节点到当前结点形成的路径下,能否向左(加入”(“)或能否向右(加入”)“)。以及访问到路径终点的判断条件.

我们在进行括号匹配时,要遵循的原则是:在插入”)“时,前面必须有未匹配的”(“存在。在插入”(“时,必须已插入的”(“数量没达到给定值。

实现:

  void dfs(vector<string> &re, string& cur_re, int unmatched_lefts, int added_lefts, int n)
{

	if(unmatched_lefts == 0 && added_lefts == n)
	{
		re.push_back(cur_re);
	}

	if(unmatched_lefts > 0){//insert ')' is ok
		cur_re.append(1, ')');
		dfs(re, cur_re, unmatched_lefts - 1, added_lefts, n);
	}

	if(cur_re.size() > 0 && added_lefts < n)//can add another '('
	{
		cur_re.append(1,'(');
		dfs(re, cur_re, unmatched_lefts + 1, added_lefts + 1, n);
	}
	cur_re.pop_back();
}
vector<string> generateParenthesis(int n) {

	vector<string> re;
	if(n <= 0)
		return re;
	string one_solve;
	one_solve.append(1, '(');
	dfs(re, one_solve, 1, 1, n);
	return re;
}

【leetcode】Generate Parentheses,布布扣,bubuko.com

时间: 05-28

【leetcode】Generate Parentheses的相关文章

【LeetCode】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: "((()))", "(()())", "(())()", "()(())", "()()()" [思

【LeetCode】Generate Parentheses (2 solutions)

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

【Leetcode】Generate Parentheses in JAVA

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: "((()))", "(()())", "(())()", "()(())", "()()()" 用dfs思想做

【leetcode】 Generate Parentheses (middle)☆

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】Valid Parentheses

Given a string containing just the characters '(', ')', '{', '}', '[' and ']', determine if the input string is valid. The brackets must close in the correct order, "()" and "()[]{}" are all valid but "(]" and "([)]"

【LeetCode】Valid Parentheses合法括号

给定一个仅包含 '('.')'.'{'.'}'.'['.']'的字符串,确定输入的字符串是否合法. e.g. "()"."()[]{}"."[()]([]({}))" 是合法的,而"(]"."([)]" 是不合法的. 使用栈stack C++实现: 1 bool isValid(string s) { 2 stack<char> stack; 3 for (char &c : s) {

【LeetCode】- Valid Parentheses(有效的括号)

[ 问题: ] Given a string containing just the characters '(', ')', '{', '}', '[' and ']', determine if the input string is valid. 直译:给定一个字符串,该串包含字符'(', ')', '{', '}', '[', ']', 请判断它是不是有效的 The brackets must close in the correct order, "()" and "

【LeetCode】字符串 string(共112题)

p.p1 { margin: 0.0px 0.0px 0.0px 0.0px; font: 12.0px Helvetica } [3]Longest Substring Without Repeating Characters [5]Longest Palindromic Substring [6]ZigZag Conversion [8]String to Integer (atoi) [10]Regular Expression Matching [12]Integer to Roman

【LeetCode】回溯法 backtracking(共39题)

p.p1 { margin: 0.0px 0.0px 0.0px 0.0px; font: 12.0px Helvetica } [10]Regular Expression Matching [17]Letter Combinations of a Phone Number [22]Generate Parentheses (2019年2月13日) 给了一个N,生成N对括号的所有情况的字符串. n = 3 [ "((()))", "(()())", "(