leetcode - [22] Generate Parentheses

2020/06/19

问题描述

Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses.

给你n对圆括号,请输出所有符合要求的组合。

要求是什么呢?

输出右括号前,一定要有左括号。

举个例子:

n = 3

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

Update at 2020_0908

重新梳理一下思路:

首先,我们需要明确一个合法的括号字符串需要满足两条性质:

第一,任意前缀中左括号的数量大于等于右括号的数量。

第二,左右括号数量相等。

然后,我们考虑放置左右括号的时机:

只要有剩余的左括号,就都可以放在当前位置: lc < n

但是放置右括号的条件就比较严格:

不仅需要有剩余右括号,同时需要保证已有左括号的数量大于右括号。

rc < n && lc > rc

来看下示意图:

再来看下完整实现:

class Solution {

    List<String> ans = new LinkedList<>();

    private void dfs(int n, int lc, int rc, StringBuilder sb){
        if (lc == n && rc == n){
            ans.add(new String(sb));
            return;
        }

        if (lc < n) {
            dfs(n, lc + 1, rc, sb.append('('));
            sb.setLength(sb.length() - 1);
        }
        if (rc < n && lc > rc){
            dfs(n, lc, rc + 1, sb.append(')'));
            sb.setLength(sb.length() - 1);
        }
    }

    public List<String> generateParenthesis(int n) {
        dfs(n, 0, 0, new StringBuilder());
        return ans;
    }
}

解法1

Thanks

Generate All Strings With n Matched Parentheses - Backtracking

@yfcheng

最好先看下视频中的讲解。

思路是这样的:

首先,初始情况下,左、右括号的数量都为0

左括号的已用数量用open表示,右括号用close表示。

然后,左括号只要在最大限制n之内,都能用。

所以:

if (open < max){
    bt(ans, open + 1, close, max, sb.append('('));
    ...
}

再来,对于右括号而言,就有限制了,只有当已用左括号的数量大于已用右括号的数量时,

才能用右括号。

if (open > close){
    bt(ans, open, close + 1, max, sb.append(')'));
    ...
}

然后,再考虑下这道题的目标是什么?

输出所有符合要求的圆括号组合。

因为我们上面的两个限制条件,所以在递归过程中,我们的组合肯定是符合要求的。

那么我们就要去判断它的长度是否也满足要求。

if ((sb.length() >>> 1) == max){
    ans.add(new String(sb));
    return;
}

最后,由于StringBuilder是一个引用变量,所以在递归过程中,一旦当前递归函数结束后,需要删除最后一个字符。

来看下实现:

class Solution {
    public List<String> generateParenthesis(int n) {
        
        List<String> ans = new LinkedList<>();
        bt(ans, 0, 0, n, new StringBuilder());
        return ans;
    }
    
    private void bt(List<String> ans, int open, int close, int max, StringBuilder sb){
        
        if ((sb.length() >>> 1) == max){
            ans.add(new String(sb));
            return;
        }
        
        if (open < max){
            bt(ans, open + 1, close, max, sb.append('('));
            // sb.setLength(sb.length() - 1);
            sb.deleteCharAt(sb.length() - 1);
        }
        if (open > close){
            bt(ans, open, close + 1, max, sb.append(')'));
            sb.setLength(sb.length() - 1);
        }
    }
}

Enjoy it !


一位喜欢提问、尝试的程序员

(转载本站文章请注明作者和出处 姚屹晨-yaoyichen

Post Directory