首页 > 代码库 > LeetCode: Generate Parentheses 解题报告
LeetCode: Generate Parentheses 解题报告
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:
"((()))", "(()())", "(())()", "()(())", "()()()"
Hide Tags Backtracking String
SOLUTION 1:
我们还是使用九章算法的递归模板。
1. Left代表余下的‘(‘的数目
2. right代表余下的‘)‘的数目
3. 注意right余下的数目要大于left,否则就是非法的，比如，先放一个‘)‘就是非法的。
4. 任何一个小于0，也是错的。
5. 递归的时候，我们只有2种选择，就是选择‘(‘还是选择‘)‘。
6. 递归的时候，一旦在结果的路径上尝试过‘(‘还是选择‘)‘，都需要回溯，即是sb.deleteCharAt(sb.length() - 1);
1 public class Solution { 2 public List<String> generateParenthesis(int n) { 3 List<String> ret = new ArrayList<String>(); 4 5 if (n == 0) { 6 return ret; 7 } 8 9 dfs(n, n, new StringBuilder(), ret);10 11 return ret;12 }13 14 // left : the left Parentheses15 // right : the right Parentheses16 public void dfs(int left, int right, StringBuilder sb, List<String> ret) {17 if (left == 0 && right == 0) {18 ret.add(sb.toString());19 return;20 }21 22 // left < right means that we have more ( then we can add ).23 if (left < 0 || right < 0 || left > right) {24 return;25 }26 27 dfs(left - 1, right, sb.append(‘(‘), ret);28 sb.deleteCharAt(sb.length() - 1);29 30 dfs(left, right - 1, sb.append(‘)‘), ret);31 sb.deleteCharAt(sb.length() - 1);32 }33 }
主页君的GITHUB:
https://github.com/yuzhangcmu/LeetCode_algorithm/blob/master/string/GenerateParenthesis.java
LeetCode: Generate Parentheses 解题报告
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。