LeetCode-22. Generate Parentheses

[ninehills]

问题

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:

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

思路

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

• 递归思路
  • 从n=2，很难推导出n=3；此时应该换个思路，我们找的其实是generateParenthesis(n, open)，其中n是闭合的括号对数目，open是没有闭合的右括号的数目（其实这里open左右都无所谓，假设所有没有闭合的都只有右括号）；最终我们找的只是open = 0 的特殊情况
  • 如果 n 等于 0 ，返回 [ ')' * open ]
  • 如果 open 等于 0 ，返回 ['('+x for x in generateParenthesis(n-1, 1)]，就是对所有『n-1个闭合括号对&1个右括号』的组合，都在最左侧加一个左括号
  • 如果 open 不为 0，应该是两种情况的组合
    • [')'+x for x in self.generateParenthesis(n, open-1)]，『n个闭合括号+ n-1个右括号』加一个最左侧的右括号
    • ['('+x for x in self.generateParenthesis(n-1, open+1)]，『n-1个闭合括号 + n +1 个右括号』加一个最左侧的左括号
• 动态规划，要想得到n对括号，那么应该有这么几步
  • 首先产生一对括号()
  • 括号里放0对括号，括号后放n-1对括号：'(' + parenthesis(0) + ')' + parenthesis(n-1)
  • 括号里放1对，括号后放 n-2对：'(' + parenthesis(1) + ')' + parenthesis(n-2)
  • .....以此类推，注意parenthesis(0) 为''
  • 括号里放n-1对括号，括号后放 0对：'(' + parenthesis(n-1) + ')' + parenthesis(0)

解答

递归思路（直接复制别人的代码）

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]

#4 20170731