当前位置 : 首页 » 文章分类 :  算法  »  LeetCode.022.Generate Parentheses 括号生成

LeetCode.022.Generate Parentheses 括号生成

题目描述

22 Generate Parentheses
https://leetcode-cn.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:

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

解题过程

排列组合类题目,首先想到的就是 回溯法 backtracking,对于每个位置,可以选择 左括号 或者 右括号,但这个选择是有限制的,只有已选择的有多余要匹配的左括号才能选右括号。
用一个双端队列 deque 保存已选择的部分(用 StringBuilder 也可以),变量 leftCount 记录已选择部分中左括号个数,当 deque 里左括号比右括号多时,可以选择右括号
结束条件:已经选择了 n 个左括号,则剩余一定全是右括号,直接补全右括号后加入结果集即可。当然,当 deque 中元素个数为 2n 时也结束。

时间复杂度很难分析,空间复杂度 O(n)

private static class SolutionV2020 {
    Set<String> res; // 最终结果集
    int n;
    public List<String> generateParenthesis(int n) {
        this.n = n;
        this.res = new HashSet<>();
        // n为1时特例处理
        if (n == 1) {
            List<String> trivial = new ArrayList<>();
            trivial.add("()");
            return trivial;
        }
        // 用一个双端队列 deque 保存已选择的部分
        Deque<String> deque = new LinkedList<>();
        deque.offer("("); // 第一个元素一定是左括号
        // 回溯生成括号
        backtrack(deque, 1);
        return new ArrayList<>(res);
    }

    // 回溯生成括号,deque 是当前已选择的部分, leftCount 是已选择部分中左括号个数
    private void backtrack(Deque<String> deque, int leftCount) {
        if (deque.size() == n * 2) {
            res.add(deque.stream().collect(Collectors.joining()));
            return;
        }
        // 已经选择了 n 个左括号,则剩余一定全是右括号
        if (leftCount == n) {
            String newParent = deque.stream().collect(Collectors.joining());
            for (int i = deque.size(); i < n * 2; i++) {
                newParent += ")";
            }
            res.add(newParent);
            return;
        }
        if (leftCount < n) {
            // 选择左括号
            deque.offer("(");
            backtrack(deque, leftCount + 1);
            // 回溯(撤回)
            deque.pollLast();

            // 当 deque 里左括号比右括号多时,可以选择右括号
            if (leftCount > deque.size() - leftCount) {
                // 选择右括号
                deque.offer(")");
                backtrack(deque, leftCount);
                // 回溯
                deque.pollLast();
            }
        }
    }
}

GitHub代码

algorithms/leetcode/leetcode/_022_GenerateParentheses.java
https://github.com/masikkk/algorithms/blob/master/leetcode/leetcode/_022_GenerateParentheses.java


上一篇 LeetCode.151.Reverse Words in a String 翻转字符串里的单词

下一篇 LeetCode.剑指offer.013.机器人的运动范围

阅读
评论
539
阅读预计2分钟
创建日期 2020-04-09
修改日期 2020-04-09
类别

页面信息

location:
protocol:
host:
hostname:
origin:
pathname:
href:
document:
referrer:
navigator:
platform:
userAgent:

评论