ninehills / blog

https://ninehills.tech
862 stars 80 forks source link

LeetCode-22. Generate Parentheses #35

Closed ninehills closed 7 years ago

ninehills commented 7 years ago

问题

https://leetcode.com/problems/generate-parentheses/ Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses.

For example, given n = 3, a solution set is:

[
  "((()))",
  "(()())",
  "(())()",
  "()(())",
  "()()()"
]

思路

两种思路,一种是递归,一种是动态规划

解答

递归思路(直接复制别人的代码)

class Solution:
    def generateParenthesis(self, n, open=0):
        if n == 0: return [')'*open]
        if open == 0:
            return ['('+x for x in self.generateParenthesis(n-1, 1)]
        else:
            return [')'+x for x in self.generateParenthesis(n, open-1)] + ['('+x for x in self.generateParenthesis(n-1, open+1)]

动态规划(更容易理解,也是复制别人的代码)

# https://discuss.leetcode.com/topic/28374/clean-python-dp-solution
class Solution(object):
    def generateParenthesis(self, n):
        """
        :type n: int
        :rtype: List[str]
        """
        dp = [[] for i in range(n + 1)]
        dp[0].append('')
        for i in range(n + 1):
            for j in range(i):
                dp[i] += ['(' + x + ')' + y for x in dp[j] for y in dp[i - j - 1]]
        return dp[n]
ninehills commented 7 years ago

4 20170731