LeetCode：22. Generate Parentheses（生成匹配括号）

本是古典何须时尚 2022-04-04 06:14 201阅读 0赞

> **文章最前**： 我是Octopus，这个名字来源于我的中文名--章鱼；我热爱编程、热爱算法、热爱开源。所有源码在我的个人[github][] ；这博客是记录我学习的点点滴滴，如果您对 Python、Java、AI、算法有兴趣，可以关注我的动态，一起学习，共同进步。

**相关文章：**

1.  **[LeetCode：55. Jump Game（跳远比赛）][LeetCode_55. Jump Game]**
2.  **[Leetcode：300. Longest Increasing Subsequence（最大增长序列）][Leetcode_300. Longest Increasing Subsequence]**
3.  **[LeetCode：560. Subarray Sum Equals K（找出数组中连续子串和等于k][LeetCode_560. Subarray Sum Equals K_k]**

--------------------

**文章目录：**

题目描述：

java实现方法1：

python实现方式1：

源码github地址：https://github.com/zhangyu345293721/leetcode

--------------------

### 题目描述： ###

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

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

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

著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

--------------------

### java实现方法1： ###

/**
         * 生成括号
         *
         * @param n 输入字符
         * @return list
         */
        private List<String> generateParentheses(int n) {
            if (n < 1) {
                return new ArrayList<>();
            }
            List<String> result = new ArrayList<>();
            bracketTrace(result, "", 0, 0, n);
            return result;
        }
    
        /**
         * 括号位置追加
         *
         * @param result 结果
         * @param s      字符串
         * @param left   左边
         * @param right  右边
         * @param n      下标
         */
        private void bracketTrace(List<String> result, String s, int left, int right, int n) {
            if (s.length() == n * 2) {
                result.add(s);
                return;
            }
            if (left < n) {
                bracketTrace(result, s + "(", left + 1, right, n);
            }
            if (right < left) {
                bracketTrace(result, s + ")", left, right + 1, n);
            }
        }

时间复杂度：O(n^2)

空间复杂度：O(n)

--------------------

### python实现方式1： ###

def generate_parentheses(self, n: int) -> List[str]:
            '''
                按照要求生成括号字符串
            Args:
                n: 括号对长度
            Returns:
                链表
            '''
            result = []
            if n < 1:
                return result
            self.bracket_trace(result, '', 0, 0, n)
            return result
    
        def bracket_trace(self, result, s: str, left: int, right: int, n: int):
            '''
                递归遍历括号
            Args:
                result: 结果集
                s: 字符串
                left: 左边
                right: 右边
                n: 长度
            '''
            if (len(s) == 2 * n):
                result.append(s)
            if left < n:
                self.bracket_trace(result, s + '(', left + 1, right, n)
            if right < left:
                self.bracket_trace(result, s + ')', left, right + 1, n)

时间复杂度：O(n^2)

空间复杂度：O(n)

--------------------

### 源码github地址： ###

[https://github.com/zhangyu345293721/leetcode][https_github.com_zhangyu345293721_leetcode]

[github]: https://github.com/zhangyu345293721
[LeetCode_55. Jump Game]: https://blog.csdn.net/zy345293721/article/details/84991870
[Leetcode_300. Longest Increasing Subsequence]: https://blog.csdn.net/zy345293721/article/details/84984249
[LeetCode_560. Subarray Sum Equals K_k]: https://blog.csdn.net/zy345293721/article/details/84952201
[https_github.com_zhangyu345293721_leetcode]: https://github.com/zhangyu345293721/leetcode