首页 > 代码库 > 【LeetCode】Generate Parentheses (2 solutions)
【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:
"((()))", "(()())", "(())()", "()(())", "()()()"
解法一：递归
借助栈，‘(‘、‘)‘构成一对分别进出栈。最后栈为空，则输入括号构成的字符串是合法的。
class Solution {public: vector<string> generateParenthesis(int n) { vector<string> result; if(n == 0) return result; //first must be ‘(‘ string cur = "("; stack<char> s; s.push(‘(‘); Helper(result, cur, s, 2*n-1); return result; } void Helper(vector<string>& result, string cur, stack<char> s, int num) { if(num == 1) {//must be ‘)‘ if(s.top() == ‘(‘ && s.size() == 1) {//all matched cur += ‘)‘; result.push_back(cur); } } else { //‘(‘ always push string str1 = cur; str1 += ‘(‘; s.push(‘(‘); Helper(result, str1, s, num-1); s.pop(); //‘)‘ if(!s.empty()) {//prune. never begin with ‘)‘ string str2 = cur; str2 += ‘)‘; if(s.top() == ‘(‘) s.pop(); //check empty() before access top() else s.push(‘)‘); Helper(result, str2, s, num-1); } } }};
解法二：递归
稍作分析可知，栈是不必要的，只要记录字符串中有几个‘(‘，记为count。
每进入一个‘(‘, count ++. 每匹配一对括号, count--。
最终全部匹配，需要count==0
class Solution {public: vector<string> generateParenthesis(int n) { vector<string> result; if(n == 0) return result; //first must be ‘(‘ string cur = "("; int count = 1; //number of (‘s in cur Helper(result, cur, count, 2*n-1); return result; } void Helper(vector<string>& result, string cur, int count, int num) { if(num == 1) {//must be ‘)‘ if(count == 1) {//all matched cur += ‘)‘; result.push_back(cur); } } else { //‘(‘ always push string str1 = cur; str1 += ‘(‘; count ++; Helper(result, str1, count, num-1); count --; //‘)‘ if(count != 0) {//prune. never begin with ‘)‘ string str2 = cur; str2 += ‘)‘; count --; Helper(result, str2, count, num-1); } } }};
【LeetCode】Generate Parentheses (2 solutions)
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。