【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:

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

思路:产生所有合理的括号配对

我自己用的回溯法,遍历所有压入第k个')'时前面'('个数

class Solution {
public:
vector<string> generateParenthesis(int n) {
vector<string> ans;
if(n == )
return ans; vector<vector<char>> S(n); //放入第k个右括号时,已经放入的左括号数目
int k = ;
for(int i = k + ; i <= n; i++)
{
S[k].push_back(i);
}
string X;
while(k >= )
{
while(!S[k].empty())
{
int numOfLeftP = getNumOfLeft(X); //还没有放入的左括号数目
while(numOfLeftP < S[k].back()) //如果X中"("少于需要的,压入"("
{
X.append("(");
numOfLeftP++;
}
while(numOfLeftP > S[k].back()) //如果X中"("多于需要的,弹出
{
char back = X.back();
X.pop_back();
if(back == '(')
{
numOfLeftP--;
}
}
X.append(")"); //压入新的")"
int back = S[k].back();
S[k].pop_back(); if(k < n - )
{
k++;
int num = max(back, k + ); //可以选择的已有左括号数必须大于当前已有的 小于等于n
for(int i = num; i <= n; i++)
{
S[k].push_back(i);
}
}
else
{
ans.push_back(X);
}
}
k--;
}
return ans;
} int getNumOfLeft(string X)
{
int position=;
int i=;
while((position=X.find_first_of("(",position))!=string::npos)
{
position++;
i++;
}
return i;
} };

我的思路很繁琐,中间要做各种判断,看下大神的。

产生长度为 2*n的括号, 但是不能随便产生

设len是当前的字符串长度, v是当前完整配对的括号对数

如果 len - v < n 还可以放入'('

如果 2 * v < len 还可以放入')'

当长度符合条件就压入答案,只有这时stack长度才会减小,其他长度下会压入新值。

vector<string> generateParenthesis2(int n) {
vector<string> ans;
vector<string> stack;
vector<int> validationStack;
stack.push_back("(");
validationStack.push_back();
while(stack.size() != )
{
string s = stack.back();
stack.pop_back();
int v = validationStack.back();
validationStack.pop_back();
if(s.length() == * n)
{
ans.push_back(s);
continue;
}
if(s.length() - v < n)
{
stack.push_back(s.append("("));
validationStack.push_back(v);
s.pop_back();
}
if( * v < s.length())
{
stack.push_back(s.append(")"));
validationStack.push_back(v + );
s.pop_back();
}
}
return ans; }
上一篇:[C# WPF]MoeEroViewer Developing Log


下一篇:炫酷的时钟--canvas初体验