710 - Python LeetCode

【Leetcode】python - [22] Generate Parentheses 個人解法筆記

題目出處

22. Generate Parentheses

難度

medium

個人範例程式碼

class Solution:
    def generateParenthesis(self, n: int) -> List[str]:

        ans = []
        self.dfs(n, n, "", ans)
        return ans

    def dfs(self, left, right, current_str, ans):
        # end of recursion
        if left == 0:
            for _ in range(right):
                current_str += ")"
            ans.append(current_str)
            return

        # define and split
        if left >= 0:
            self.dfs(left-1, right, current_str + "(", ans)

        if right > left: # (3, 2), (3, 1)
            self.dfs(left, right-1, current_str + ")", ans)

        return

最近在練習程式碼本身就可以自解釋的 Coding style，可以嘗試直接閱讀程式碼理解

算法說明

用 dfs 把所有狀況窮舉出來，我們以 left, right 代替左右括弧剩餘的數量，

  • 可新增 left 的條件：left > 0

  • 可新增 right 的條件：right > left # (3, 2), (3, 1)

  • 終止條件：left = 0，放上所有剩餘的 right

input handling

一同在 dfs 內處理，基本上是處理 n = 0 的情況

Boundary conditions

用 dfs 控制範圍，終止條件為當 left = 0

Reference