区块链技术博客
www.b2bchain.cn

22. 括号生成回溯string stringbuilder

这篇文章主要介绍了22. 括号生成回溯string stringbuilder,通过具体代码讲解8159并且分析了22. 括号生成回溯string stringbuilder的详细步骤与相关技巧,需要的朋友可以参考下

本文实例讲述了22. 括号生成回溯string stringbuilder。分享给大家供大家参考文章查询地址https://www.b2bchain.cn/8159.html。具体如下:

22. 括号生成 

 //数字 n 代表生成括号的对数,请你设计一个函数,用于能够生成所有可能的并且 有效的 括号组合。  // //  // // 示例:  // // 输入:n = 3 //输出:[ //       "((()))", //       "(()())", //       "(())()", //       "()(())", //       "()()()" //     ] //  // Related Topics 字符串 回溯算法  // 👍 1205 👎 0   //leetcode submit region begin(Prohibit modification and deletion) import java.util.ArrayList; import java.util.List;  public class Solution {      public List<String> generateParenthesis(int n) {         List<String> res = new ArrayList<>();         if (n == 0) {             return res;         }          StringBuilder path = new StringBuilder();         dfs(path, n, n, res);         return res;     }      private void dfs(StringBuilder path, int left, int right, List<String> res) {         if (left == 0 && right == 0) {             res.add(path.toString());             return;         }          // 剪枝(如图,左括号可以使用的个数严格大于右括号可以使用的个数,才剪枝,注意这个细节)         if (left > right) {             return;         }          if (left > 0) {             path.append("(");             dfs(path, left - 1, right, res);             path.deleteCharAt(path.length() - 1);         }          if (right > 0) {             path.append(")");             dfs(path, left, right - 1, res);             path.deleteCharAt(path.length() - 1);         }     } } //leetcode submit region end(Prohibit modification and deletion) 

 

 class Solution {     public List<String> generateParenthesis(int n) {         List<String> ans=new ArrayList<>();         if (n==0) return ans;         dfs("",n,n,ans);         return ans;     }     private void dfs(String curStr,int left,int right, List<String> ans){          if(left==0 && right==0) {                ans.add(curStr); return;          }          if(left>right) return;                    //直接操作string 每次进入相当于new一个新的 所以无需回溯         if(left>0) dfs(curStr+"(",left-1,right,ans);         if(right>0) dfs(curStr+")",left,right-1,ans);     } }

 

本文地址https://www.b2bchain.cn/8159.html

赞(0) 打赏
部分文章转自网络,侵权联系删除b2bchain区块链学习技术社区 » 22. 括号生成回溯string stringbuilder
分享到: 更多 (0)

评论 抢沙发

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址

b2b链

联系我们联系我们