Leetcode 22 Generate Parentheses

发表于 |

给出 n 代表生成括号的对数，请你写出一个函数，使其能够生成所有可能的并且有效的括号组合。

例如，给出 n = 3，生成结果为：
[
“((()))”,
“(()())”,
“(())()”,
“()(())”,
“()()()”
]

题意分析：
要我们找出所有合法的包括n对括号的字符串！

思路分析：
当碰到这道题的时候，应该如何去思考呢？就拿n=3当例子，显然，我们不能凭空构造，我们将n=3结果分解一下，发现有以下几种情况:

  1. ‘(‘ + ss + ‘)’
  2. ‘()’ + ss
  3. ss + ‘()’

其中ss是拥有两队括号的合法字符串，突然发现好像找到规律了。
我们定义f(3)表示n=3时题目的答案，那么有：
f(3) = '(' + ss + ')' , '()' + ss, ss + '()' for ss in f(2)

但是如果就直接单纯的以为答案就是按照上面三种情况依次累加的话就错了（我就犯了这个错误）
例如对于n=4，有’(())(())’，这种情况是无法通过之前说的三种模式构造出来的。我们可以看出'(())(())'是可以分解成两个 n=2的情况，很容易想到:
f(4) = f(1) 组合 f(3) + f(2) 组合 f(2)

注意到会存在重复计算，所以使用一下记忆化的思想。并且单独考虑 '(' + ss + ')'这种情况。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
# 36ms, beats 16.54%
cache = {}
class Solution(object):
    def generateParenthesis(self, n):
        if n == 1: return ['()']
        if n in cache: return cache[n]
        s = set()
        for i in range(1, n):
            for s1 in self.generateParenthesis(i):
                for s2 in self.generateParenthesis(n-i):
                    if i == 1:
                        s.add('(' + s2 + ')')
                    s.add(s1+s2)
        cache[n] = list(s)
        return cache[n]

以上属于我的肤浅想法，实际有大神真就凭空把所有的结果构造出来了

1
2
3
4
5
6
7
8
class Solution(object):
    def generateParenthesis(self, n):
        def generate(p, left, right, parens=[]):
            if left:         generate(p + '(', left-1, right)
            if right > left: generate(p + ')', left, right-1)
            if not right:    parens += p,
            return parens
        return generate('', n, n)