Leetcode Python - 22. Generate Parentheses

Leetcode #22 - Generate Parentheses

이번에는 특정 챕터별로 문제들을 풀어보겠습니다. dynamic programming를 집중적으로 풀어보겠습니다.

리트코드의 문제 22 ‘Generate Parentheses’을 파이썬으로 풀어 보도록 하겠습니다. f(n-1)에서 각 string index에 ()를 넣어가면서 구합니다.

전체 코드는 아래와 같습니다.

class Solution:
    def generateParenthesis(self, n):
        if n == 1:
            return ["()"]
        elif n == 2:
            return ["()()","(())"]
        dp = [["()"], ["()()","(())"]]

        for i in range(3, n+1):
            tmp = []
            for j in dp[-1]:
                for k in range(len(j)):
                    if not j[:k]+"()" + j[k:] in tmp:
                        tmp.append( j[:k]+"()" + j[k:] )
            dp.append(tmp)
        return dp[-1]

시간복잡도는 O(n) : n * 2^(n-1) * 2(n-1) = n² * 2ⁿ n : 최초 loop 2^(n-1) : 두번째 loop : n-1번째의 총 개수, 최악의 경우 2의 거듭제곱 (물론 중복 제거해야하지만) 2(n-1) : 세번째 loop : 각 n-1번째의 값의 길이 (e.g n=2 (()))

공간복잡도는 O(2ⁿ) : 2^0 + 2^1 + … 2^n = 2^(n+1)-1