https://leetcode-cn.com/problems/generate-parentheses/
# -*- coding:utf-8 -*- class Solution(object): def generateParenthesis(self, n): """ :type n: int :rtype: List[str] """ if n == 0: return [''] if n == 1: return ['()'] res = ['()'] for i in range(n - 1): temp_list = [] for each in res: for j in range(len(each)): temp_str = each[:j + 1] + '()' + each[j + 1:] print(each, temp_str) temp_list.append(temp_str) res = temp_list res_fin = [] for each in res: if each not in res_fin: res_fin.append(each) return res_fin pass if __name__ == '__main__': n = 3 print(Solution().generateParenthesis(n))
思路:在上一个答案的每一个字符中再加一个()然后去重。比如当n==2时,就是在n==1的结果()中 再(前加一个(),在()中加一个括号,在)后加一个括号以求的n==2时的答案。
但是这种方法复杂度略高,没办法通过所有的用例,最后一个用例因为超时会不能AC。
思考:有一种改进就是使用递归的思想求解。
def generateParenthesis1(self, n):
"""
:type n: int
:rtype: List[str]
"""
if n == 0:
return [""]
elif n == 1:
return ["()"]
elif n == 2:
return ["()()", "(())"]
result = []
for i in range(n):
j = n - 1 - i
temp1 = self.generateParenthesis(i)
temp2 = self.generateParenthesis(j)
result.extend(["(%s)%s" % (p, q) for p in temp1 for q in temp2])
return result
可以AC全部用例。
0 条评论