22. 括号生成

发表评论
349 views

 ›
22. 括号生成

官方链接

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

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

例如，给出 n = 3，生成结果为：

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

思路

  1. 数学归纳法

    n = 1 () n = 2 ()() | (())

  2. 递归的搜索方式

字符串的长度 为 2n O(2^(2n))

  1. 在 2 的基础上剪枝

left 随时加，只要别超标
right 左个数>右个数

解法一

剪枝

class Solution {
  private List<string> result;

  public List<string> generateParenthesis(int n) {
    result = new ArrayList<String>();
    _generate(0,0,n, "");
    return result;
  }

  public void _generate(int left, int right, int n, String s) {
    // terminator
    if (left == n && right == n) {
      result.add(s);
      return;
    }

    // process current logic: left, right

    // drill down
    if(left < n) 
      _generate(left+1, right , n, s, "(");

    if (left > right)
      _generate(left, right+1 , n, s, ")");

    // reverse states
  }
}

class Solution {
    public List<String> generateParenthesis(int n) {

        List<String> result = new ArrayList<>();
        generate(result, n, 0, 0, "");
        return result;
    }

    private void generate(List<String> result, int n, int left, int right, String s) {
        if (left == n && right == n) {
            result.add(s);
            return;
        }

        if (left < n) generate(result, n, left + 1, right, s + '(');
        if (right < left) generate(result, n, left, right + 1, s+')');
    }
}

class Solution:
    def generateParenthesis(self, n: int) -> List[str]:
      self.generate(0, 0, n, "")
      return None

    def generate(self, left, right, n, s):
      # terminator
      if left == n and right == n:
        print(s)        
        return
      # process
      # s1 = s + '('
      # s2 = s + ')'

      # drill down
      if left < n:
        self.generate(left+1, right, n, s+'(')
      if left > right:
        self.generate(left, right+1, n, s+')')
      # reverse states

解法二

动态规划

先确定最左边的括号一定是左括号, 给他匹配一个右括号, 则 其它 n-1个括号要么在这一对括号内, 要么在这一对括号的右边

class Solution {

    public List<String> generateParenthesis(int n) {

        List<List<String>> result = new ArrayList<>();
        if (n == 0) return result.get(0);

        // 零组括号 n = 0
        List<String> zero = new ArrayList<>();
        zero.add("");
        result.add(zero);

        // 一组括号 n = 1
        List<String> one = new ArrayList<>();
        one.add("()");
        result.add(one);

        for(int i = 2; i <= n; i++) {  // 开始遍历 p q, 其中 p+q = i-1, j 作为索引
            List<String> tmp = new ArrayList<>(); 
            for (int j = 0; j < i; j++) {
                List<String> str1 = result.get(j); // p = j 时的括号组合情况
                List<String> str2 = result.get(i-1-j); // q = (i-1) - j 时的括号组合情况
                for (String s1 : str1) {
                    for (String s2 : str2) {
                        String el = "(" + s1 + ")" + s2;
                        tmp.add(el);
                    }
                }
            }
            result.add(tmp);
        }
        return result.get(n);
    }
}