leetcode 22. Generate Parentheses
leetcode 22. Generate Parentheses
Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses.
Example 1:
Input: n = 3 Output: ["((()))","(()())","(())()","()(())","()()()"] Example 2:
Input: n = 1 Output: ["()"]
Constraints:
1 <= n <= 8
python 解法
p is the parenthesis-string built so far, left and right tell the number of left and right parentheses still to add, and parens collects the parentheses.
Solution 1
def generateParenthesis(self, n):
def generate(p, left, right, parens=[]):
if left: generate(p + '(', left-1, right)
if right > left: generate(p + ')', left, right-1)
if not right: parens += p,
return parens
return generate('', n, n)Solution 2
Here I wrote an actual Python generator. I allow myself to put the yield q at the end of the line because it’s not that bad and because in “real life” I use Python 3 where I just say yield from generate(…).
def generateParenthesis(self, n):
def generate(p, left, right):
if right >= left >= 0:
if not right:
yield p
for q in generate(p + '(', left-1, right): yield q
for q in generate(p + ')', left, right-1): yield q
return list(generate('', n, n))Solution 3
Improved version of this. Parameter open tells the number of “already opened” parentheses, and I continue the recursion as long as I still have to open parentheses (n > 0) and I haven’t made a mistake yet (open >= 0).
def generateParenthesis(self, n, open=0):
if n > 0 <= open:
return ['(' + p for p in self.generateParenthesis(n-1, open+1)] + \
[')' + p for p in self.generateParenthesis(n, open-1)]
return [')' * open] * (not n)c++ 解法
class Solution {
public:
vector<string> ans;
void f(string s,int open,int close){ //open => '(' count remaining
if(open==0&&close==0){ //close=> ')' count remaining
ans.push_back(s);
return;
}
if(open>0)f(s+"(",open-1,close);
if(open<close)f(s+")",open,close-1); //'(' must be placed before ')'
}
vector<string> generateParenthesis(int n) {
ans.clear();
f("",n,n); //Balanced string will have
return ans; //n-open and n-closing brackets
}
};