leetcode - 0022 括号生成

[meishaoming]

https://leetcode-cn.com/problems/generate-parentheses/

解法一

审完题，隐约觉得这题考的是广度/深度优先搜索算法。

如果前一个括号为 (，它的下一个有两种情况，可以为 ( 也可以为 )

如果前一个括号为 ) ，且关边的 ( 和 ) 数量相同，那么它下一个只能是 (。否则也有两种情况

而总的 ( 个数是确定的，所以记录一下即可。

class Solution:
    def generateParenthesis(self, n: int) -> List[str]:
        def dfs(s, n_left, n_right, p):
            s += p
            if p == '(':
                n_left += 1
                dfs(s, n_left, n_right, ')')
                if n_left < n:
                    dfs(s, n_left, n_right, '(')
            elif p == ')':
                n_right += 1
                if n_left < n:
                    dfs(s, n_left, n_right, '(')
                    if n_left > n_right:
                        dfs(s, n_left, n_right, ')')
                else:
                    if n_right < n:
                        dfs(s, n_left, n_right, ')')

                if n_right == n_left and n_right == n:
                    ans.append(s)

刷了几天题，还是有点进步的。这题我改吧改吧也算是做出来了。

小优化

看了评论里的一个答题，思路差不多，但人家写的就简洁多了。

class Solution:
    def generateParenthesis(self, n: int) -> List[str]:
        def dfs(s, n_left, n_right):
            if n_right > n_left or n_right > n or n_left > n:
                return
            if n_left == n and n_right == n:
                ans.append(s)
                return
            dfs(s+'(', n_left+1, n_right)
            dfs(s+')', n_left, n_right+1)

        ans = []
        dfs('', 0, 0)
        return ans

小优化 2

又看到一解，边界的判断比我想的高明多了

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

        def dfs(s, n_left, n_right):
            if n_left == n and n_right == n:
                ans.append(s)
                return
            if n_left < n:
                dfs(s+'(', n_left+1, n_right)
            if n_right < n_left:
                dfs(s+')', n_left, n_right+1)

        ans = []
        dfs('', 0, 0)
        return ans