Leetcode Python - 22. Generate Parentheses

Leetcode #22 - Generate Parentheses

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

리트코드의 문제 22 ‘Generate Parentheses’을 파이썬으로 풀어 보도록 하겠습니다.

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

class Solution:
    def generateParenthesis(self, n):
        if not n:
            return []
        elif n == 1:
            return ['()']
        
        dp = ['()']
        idx = 1
        while idx < n:
            cur = []
            for element in dp:
                for e in range(len(element)+1):
                    tmp = ''
                    tmp = element[:e] + '()' + element[e:]
                    if tmp in cur:
                        continue    
                    cur.append(tmp)
            dp = cur
            idx += 1
        
        return dp

---

개선하기

class Solution:
    def generateParenthesis(self, n):
        if not n:
            return []
        ret = []
        self.dfs(n, 0, 0, '', ret)
        return ret
        
    def dfs(self, n, numOpen, numClose, path, ret):
        # terminate
        if numOpen == n and numClose == n:
            ret.append(path)
            return

        # recursion
        if numOpen < n:
            self.dfs(n, numOpen+1, numClose, path + '(', ret)
        if numClose < numOpen:
            self.dfs(n, numOpen, numClose+1, path + ')', ret)

시간복잡도는

• O(2^n) : 함수 한번 실행시마다 2번의 recursion이 실행됨

공간복잡도는

• 최악의 경우 O(2^n) : 무작위로 넣을 수 있다고 가정하면 ret의 한 element 크기 (2n)이 ‘(‘혹은 ‘)’이 계속 나온다.