括号生成

括号生成

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

示例

输入:n = 3
输出:[
       "((()))",
       "(()())",
       "(())()",
       "()(())",
       "()()()"
     ]

题解

/**
 * @param {number} n
 * @return {string[]}
 */
var generateParenthesis = function(n) {
    var target = [];
    dfs(0, 0, "", target, n);
    return target;
};

function dfs(startCount, endCount, str, target, n){
    if(str.length === n*2) {
        target.push(str);
        return 0;
    }
    if(startCount < n) dfs(startCount + 1, endCount, str + "(", target, n);
    if(endCount < startCount) dfs(startCount, endCount + 1, str + ")", target, n);
}

思路

使用回溯法,上述代码中startCount代表左括号的数量,endCount代表右括号的数量,str是缓存字符串,target是目标数组,n是括号对数数量。当进行递归时,判断在左括号数量startCount数量小于n的情况下,可以在缓存字符串加入(并将startCount + 1然后传递参数进行下一次递归,在右括号的数量少于左括号的情况下,那么可以在缓存字符串中加入)并将endCount + 1然后传递参数进行下一次递归,当字符串的长度等于n*2时结束递归并将缓存字符加入目标数组。

每日一题

https://github.com/WindrunnerMax/EveryDay

题源

https://leetcode-cn.com/problems/generate-parentheses/

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • Vue数据双向绑定原理

    Vue是通过数据劫持的方式来实现数据双向数据绑定的,其中最核心的方法便是通过Object.defineProperty()来实现对属性的劫持,该方法允许精确地添...

    WindrunnerMax
  • 顶端迭代器

    给定一个迭代器类的接口,接口包含两个方法:next()和hasNext()。设计并实现一个支持peek()操作的顶端迭代器--其本质就是把原本应由next()方...

    WindrunnerMax
  • Position定位

    CSS中position属性是比较常用的元素定位方案,position常用的取值有static、relative、absolute、fixed、sticky、i...

    WindrunnerMax
  • Java工具集-拼音工具类

    cwl_java
  • vue中computed计算属性传入参数

    做一个简单的功能,使用计算属性判断传入的字符超过了20就去掉后面的字符在尾部添加。。。

    acoolgiser
  • JS方法 - 字符串处理函数封装汇总 (更新中...)

    可返回字符串固定位置的字符的Unicode编码,这个返回值是0-65535之间的整数,如果值<=255时为英文,反之为中文。

    xing.org1^
  • 剑指Offer-表示数值的字符串

    题目描述 请实现一个函数用来判断字符串是否表示数值(包括整数和小数)。例如,字符串"+100","5e2","-123","3.1416"和"-1E-16"都表...

    武培轩
  • leetcode: explore-array-29 两数之和

    https://leetcode-cn.com/explore/interview/card/top-interview-questions-easy/1/ar...

    用户7685359
  • 关于复选框checkbox没有选中不能获取值的问题

    大家应该在获取checkbox值的时候发现没有选中是没有值的,value这个值选中才会有,那该怎么让它不选中也获取呢?

    仙士可
  • Flume-NG源码分析-整体结构及配置载入分析

    终于开始Flume源码的分析研究工作了,我也是边学边和大家分享,内容上难免有不足之处,望大家见谅。

    小程故事多

扫码关注云+社区

领取腾讯云代金券