m*********a
发帖数: 3299 | 1 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:
"((()))", "(()())", "(())()", "()(())", "()()()"
递归很容易
void generateParenthesisRecr(string str,int n,int l,int r,vector&
result){
if (l==n && r==n){
result.push_back(str);
return;
}
if (l
if (l>r) generateParenthesisRecr(str+")",n,l,r+1,result);
}
vector generateParenthesis2(int n) {
vectorresult;
generateParenthesisRecr("",n,0,0,result);
return result;
}
但是不递归的我写的方法很慢，无法通过 leetcode
就是第一次插入一对"()"，下一次插入下一对的时候，可以查到
上一对的任何地方就是有三个选择(new)(),((new)),()(new)
然后插入下一对，有5*3=15中可能
插入的可能指数增长
最后去处重复
vector generateParenthesis(int n) {
stack seed;
stack solution;
vectorresult;
if (n==1){
result.push_back("()");
return result;
}
if (n==0) return result;
seed.push("()");
for (int i=2;i<=n;i++){
while (!seed.empty()){
for (int i=0;i<=seed.top().size();i++){
string str=seed.top();
solution.push(str.insert(i,"()"));
}
seed.pop();
}
seed=solution;
while (!solution.empty()) solution.pop();
}
while (!seed.empty()){
int notsame=1;
for (int i=0;i
if (seed.top()==result[i]){
seed.pop();
notsame=0;
break;
}
}
if (notsame){
result.push_back(seed.top());
seed.pop();
}
}
return result;
} | h*******e
发帖数: 1377 | | l*****a
发帖数: 14598 | 3 没细想，直接BFS就可以吧
你只能start from "("这个算root,
他的子节点可以是(( or ()
下一level可以是 ((( or (() or ()(
以此类推。只要number of "(" <= n, number of ")" <=number of "("
就可以插入Queue
最后...
combinations
【在 m*********a 的大作中提到】
: 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:
: "((()))", "(()())", "(())()", "()(())", "()()()"
: 递归很容易
: void generateParenthesisRecr(string str,int n,int l,int r,vector&
: result){
: if (l==n && r==n){
: result.push_back(str);
: return;
| l******e
发帖数: 54 | 4 一样思路改成递推就行了 空间是还可以优化的
class Solution {
public:
vector generateParenthesis(int n) {
vector f[n + 1][n + 1];
f[0][0] = vector {""};
for (int left = 0; left <= n; ++left) {
for (int right = 0; right <= left; ++right) {
for (const string& s : f[left][right]) {
if (left < n) {
f[left + 1][right].push_back(s + "(");
}
if (right < left) {
f[left][right + 1].push_back(s + ")");
}
}
}
}
return f[n][n];
}
}; | l******e
发帖数: 54 | 5 再上一个空间优化的吧
class Solution {
public:
vector generateParenthesis(int n) {
vector f[2][n + 1];
f[0][0] = vector {""};
for (int left = 0; left <= n; ++left) {
for (int right = 0; right <= left; ++right) {
f[(left + 1) & 1][right].clear();
for (const string& s : f[left & 1][right]) {
if (left < n) {
f[(left + 1) & 1][right].push_back(s + "(");
}
if (right < left) {
f[left & 1][right + 1].push_back(s + ")");
}
}
}
}
return f[n & 1][n];
}
}; | l******e
发帖数: 54 | 6 再来更多的空间优化好了
class Solution {
public:
vector generateParenthesis(int n) {
vector f[n + 1];
f[0] = vector {""};
for (int left = 0; left <= n; ++left) {
for (int right = 0; right <= left; ++right) {
for (int i = 0; i < f[right].size(); ++i) {
if (right < left) {
f[right + 1].push_back(f[right][i] + ")");
}
if (left < n) {
f[right][i] += "(";
}
}
}
}
return f[n];
}
}; | z**a
发帖数: 69 | 7 好角度，写了个，过了LC，差不多是非递归中序遍历二叉树的思路。
class Solution {
public:
class stack
{
public:
char c;
int flag;
stack(char c, int flag)
{
this->c = c;
this->flag = flag;
}
};
vector generateParenthesis(int n) {
int left = 0;
int right = 0;
vectorrecord;
vectorresult;
stack temp(0,0);
record.push_back(stack('(', 0));
left++;
while (record.size() != 0)
{
temp = record[record.size() - 1];
record.pop_back();
if (temp.c == '(')
{
left--;
}
else
{
right--;
}
if (temp.c == '(')
{
if (temp.flag == 0)
{
record.push_back(stack('(', 1));
left++;
if (left > right)
{
record.push_back(stack(')', 0));
right++;
}
}
else if (temp.flag == 1)
{
if (left < n - 1)
{
record.push_back(stack('(', 2));
left++;
record.push_back(stack('(', 0));
left++;
}
}
}
else if(temp.c == ')')
{
if (temp.flag == 0 && right!=n-1)
{
record.push_back(stack(')', 1));
right++;
if (left
{
record.push_back(stack('(', 0));
left++;
}
}
else if (temp.flag == 1)
{
if (right < n-1 && left>=right+2)
{
record.push_back(stack(')', 2));
right++;
record.push_back(stack(')', 0));
right++;
}
}
}
int pos = 0;
string temp_record;
if (right == n && left == n)
{
for (pos = 0; pos < 2*n; pos++)
{
temp_record.push_back(record[pos].c);
}
result.push_back(temp_record);
}
}
return result;
}
}; | m*********a
发帖数: 3299 | 8 大家很牛啊，想得清楚>2可能的非递归的
左右二种选择就比较难了非递归就比较难了 | m**********e
发帖数: 22 | 9 我来贡献一个用queue的方法。C#写的：
// Iterative approach
public List generateParenthesisIter(int n)
{
Queue queue = new Queue(
);
queue.Enqueue(new ParenthesisWrapper("",0,0));
List result = new List();
while (queue.Count > 0)
{
ParenthesisWrapper curr = queue.Dequeue();
if (curr.left == n)
{
if (curr.right < n)
{
curr.parenthesis += new string(')', n-curr.right);
}
result.Add(curr.parenthesis);
continue;
}
if (curr.left < n)
{
queue.Enqueue(new ParenthesisWrapper(curr.parenthesis +
"(", curr.left + 1, curr.right));
}
if (curr.right < curr.left)
{
queue.Enqueue(new ParenthesisWrapper(curr.parenthesis +
")", curr.left, curr.right + 1));
}
}
return result;
}
public class ParenthesisWrapper
{
public string parenthesis;
public int left;
public int right;
public ParenthesisWrapper(string p, int l, int r)
{
parenthesis = p;
left = l;
right = r;
}
}
combinations
【在 m*********a 的大作中提到】
: 大家很牛啊，想得清楚>2可能的非递归的
: 左右二种选择就比较难了非递归就比较难了
| m*****k
发帖数: 731 | 10 DP
combinations
【在 m*********a 的大作中提到】
: 大家很牛啊，想得清楚>2可能的非递归的
: 左右二种选择就比较难了非递归就比较难了
| l***s
发帖数: 15 | 11 贡献一个 python
class Solution:
# @param an integer
# @return a list of string
def generateParenthesis(self, n):
bs='()'
res=['()']
if n==0:
return ''
elif n==1:
return res
for i in range(2,n+1):
leres=len(res)
for j in range(leres):
base=res[0]
del res[0]
lebase=len(base)
for k in range(lebase+1):
new = base[0:k]+bs+base[k:lebase]
if not (new in res):
res.append(new)
return res |
|
