括号生成 | 徐年の博客

力扣 22. 括号生成

题目说明

数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且 有效的 括号组合。

有效括号组合需满足：左括号必须以正确的顺序闭合。

提示：
- 1 <= n <= 8

示例

示例 1:

1 2	输入：n = 3 输出：["((()))","(()())","(())()","()(())","()()()"]

示例 2:

1 2	输入：n = 1 输出：["()"]

笔者理解

此题是一道字符串算法问题，在力扣题库中被定义为中等题。

解法

当笔者阅读完此题后，采用了和电话号码的字母组合类似的队列解法，让我们来看看具体如何实现的吧。

实现

class Solution {
    /*
     * 字符串
     * 队列
     */
    public List<String> generateParenthesis(int n) {
        // 要拼接的括号数
        n = 2 * n;
        List<String> list = new ArrayList<>();
        char[] bracket = {'(', ')'};
        // 填充头部
        list.add("");

        for (int i = 0; i < n; i++) {
            int size = list.size();
            for (int j = 0; j < size; j++) {
                String temp = list.remove(0);
                for (int k = 0; k < 2; k++) {
                    // 计算当前括号组合是否合法
                    int num = 0;
                    for (int l = 0; l < temp.length(); l++) {
                        num = temp.charAt(l) == '('? num + 1: num - 1;
                    }
                    num = k == 0? num + 1: num - 1;

                    // 最后的拼接左右括号数要相等
                    if (i == n - 1) {
                        if (num == 0) {
                            list.add(temp + bracket[k]);
                        }
                    }
                    else if (num >= 0) {
                        list.add(temp + bracket[k]);
                    }
                }
            }
        }

        return list;
    }
}