(Medium #22) Generate Parentheses
Problem
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:
[
"((()))",
"(()())",
"(())()",
"()(())",
"()()()"
]
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:
[ "((()))", "(()())", "(())()", "()(())", "()()()" ]
My solution
class Solution:
def generateParenthesis(self, n):
if n==1:
return ["()"]
else:
prelist = self.generateParenthesis(n-1)
out = []
for i in range(len(prelist)):
out.append("(" + prelist[i] + ")")
for k in range(1,int(n/2)+1):
list1 = self.generateParenthesis(k)
list2 = self.generateParenthesis(n-k)
for p in range(len(list1)):
cand1 = list1[p]
for q in range(len(list2)):
cand2 = list2[q]
out.append(cand1 + cand2)
out.append(cand2 + cand1)
return list(set(out))
Runtime: 40ms, Memory: 14.1MB
def generateParenthesis(self, n):
if n==1:
return ["()"]
else:
prelist = self.generateParenthesis(n-1)
out = []
for i in range(len(prelist)):
out.append("(" + prelist[i] + ")")
for k in range(1,int(n/2)+1):
list1 = self.generateParenthesis(k)
list2 = self.generateParenthesis(n-k)
for p in range(len(list1)):
cand1 = list1[p]
for q in range(len(list2)):
cand2 = list2[q]
out.append(cand1 + cand2)
out.append(cand2 + cand1)
return list(set(out))
Other people solution
class Solution:
# @param an integer
# @return a list of string
def generateParenthesis(self, n):
result = []
def generate(result, prev, remained_front, allowed_back):
if remained_front == 0:
for i in range(allowed_back):
prev += ")"
result.append(prev)
return
if remained_front > 0:
generate(result, prev+"(", remained_front-1, allowed_back+1)
if allowed_back > 0:
generate(result, prev+")", remained_front, allowed_back-1)
generate(result,"(", n-1, 1)
return result
Runtime: 36ms, Memory: 14MB
class Solution: # @param an integer # @return a list of string def generateParenthesis(self, n): result = [] def generate(result, prev, remained_front, allowed_back): if remained_front == 0: for i in range(allowed_back): prev += ")" result.append(prev) return if remained_front > 0: generate(result, prev+"(", remained_front-1, allowed_back+1) if allowed_back > 0: generate(result, prev+")", remained_front, allowed_back-1) generate(result,"(", n-1, 1) return result
댓글
댓글 쓰기