括号生成
数字 n 代表生成括号的对数,请你设计一个函数,用于能够生成所有可能的并且 有效的 括号组合。
- 示例 1:
输入:n = 3
输出:["((()))","(()())","(())()","()(())","()()()"]
- 示例 2:
输入:n = 1
输出:["()"]
提示:
1 <= n <= 8
方法一:深度优先遍历(java)
首先我们需要知道一个结论,一个合法的括号序列需要满足两个条件:
1、左右括号数量相等
2、任意前缀中左括号数量 >= 右括号数量 (也就是说每一个右括号总能找到相匹配的左括号)
题目要求我们生成n对的合法括号序列组合,因此可以考虑使用深度优先搜索
将搜索顺序定义为枚举序列的每一位填什么,那么最终的答案一定是由n个左括号和n个右括号组成。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
|
class Solution { public List<String> generateParenthesis( int n) { List<String> ans = new ArrayList<String>(); backtrack(ans, new StringBuilder(), 0 , 0 , n); return ans; } public void backtrack(List<String> ans, StringBuilder cur, int open, int close, int max) { if (cur.length() == max * 2 ) { ans.add(cur.toString()); return ; } if (open < max) { cur.append( '(' ); backtrack(ans, cur, open + 1 , close, max); cur.deleteCharAt(cur.length() - 1 ); } if (close < open) { cur.append( ')' ); backtrack(ans, cur, open, close + 1 , max); cur.deleteCharAt(cur.length() - 1 ); } } } |
时间复杂度:o(4^n / n^(1/2))
空间复杂度:o(n)
方法一:深度优先遍历(go)
具体方法分析已在上文中表述
根据题目条件生成一颗树,并对这颗树生枝叶的条件按照题目进行限制。
需要左右括号都大于0个时才可以进行生成树的操作(等于0的特殊情况)
生成树之后生出左节点的条件:左括号的剩余数量大于0
生成树之后生成右节点条件:左括号的剩余数量 小于 右括号的剩余数量
当左右括号都为0时,为成功出口,此时进行结算,保存结果。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
|
var ans [] string var backtrack func ([] byte , int , int ) backtrack = func (bytes [] byte , left int , right int ) { if len (bytes) == 2 *n { ans = append (ans, string (bytes)) return } if left < n { bytes = append (bytes, '(' ) backtrack(bytes, left+ 1 , right) bytes = bytes[: len (bytes)- 1 ] } if right < left{ bytes = append (bytes, ')' ) backtrack(bytes, left, right + 1 ) bytes = bytes[: len (bytes)- 1 ] } } var container [] byte backtrack(container, 0 , 0 ) return ans |
时间复杂度:o(4^n / n^(1/2))
空间复杂度:o(n)
以上就是Go java 算法之括号生成示例详解的详细内容,更多关于Go java 算法括号生成的资料请关注服务器之家其它相关文章!
原文链接:https://juejin.cn/post/7126165823877545997