【LeetCode】0022 括号生成

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全部用例。