• 欢迎光临~

leetcode 22 括号生成 js 实现

开发技术 开发技术 2022-10-09 次浏览

22. 括号生成

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

示例 1:

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

示例 2:

输入:n = 1
输出:["()"]

提示:

  • 1 <= n <= 8
/**
 * @param {number} n
 * @return {string[]}
 */
 /**
 * 回溯法(DFS)
 * 把握核心规则:
 *  - 必须是有效组合,则左、右括号一定要小于n, 且右括号的数量要一直小于或等于左括号
 *  - 针对组成的括号字符串的每一个位置字符来说,要么是左括号,要么是右括号, 具体这个位置应该是左还是右,看上面的规则而定
 *  - 所以想到,我可以递归地往每个位置放左和右括号,如果违反了规则,就回溯回去,换一个放,由此想到了回溯算法
 *  - 既然是递归,首先要先想好终止条件,依题可知,如果左右括号的数量都为n的话,即为一个答案了,终止递归,返回即可
 * 解题:left 记录已经放入的左括号的数量; right 记录右括号的数量;str 表示当前组成的字符串
 */
// https://leetcode.cn/problems/generate-parentheses/solution/jsshua-ti-mian-shi-ti-jie-by-distracted-br3o6/

// 当左括号数量小于n时,可以添加一个左括号,但是括号总数不增加
// 当右括号数量小于左括号时,可以添加一个右括号,括号总数加1
// 当括号总数等于n时,返回当前缓存数组中的值
var generateParenthesis = function(n) {
    const res = [];
    // index 代表当前括号对数,left,right分别代表左右括号数,temp 代表当前生成的临时的括号数组
    const dfs = (index, left, right, temp) => {
        if(index === n){
            res.push(temp.slice().join(""));
            console.log("满足条件,回溯终止,temp",temp)
            return;
        }
        // 先判断左括号数量, 小于 n,则 push 左括号
        if(left < n){
            temp.push('(');
            // 会进入递归,直到左括号数量满足条件,结束此递归,进入下一行
            console.log("left temp",temp)
            dfs(index, left+1, right, temp);
            temp.pop(); // pop 的主要作用是回溯
            console.log("left pop temp",temp)
        }
      
        // 再判断右括号数量,小于左括号,则与左括号数量对齐,push 右括号
        if(right < left){
            temp.push(')');
            console.log("right temp",temp)
            dfs(index+1, left, right+1, temp);
            temp.pop(); // pop 的主要作用是回溯
            console.log("right pop temp",temp)
        }
    }
    dfs(0, 0, 0, []);
    return res;
};

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

程序员灯塔
转载请注明原文链接:leetcode 22 括号生成 js 实现
喜欢 (0)
违法和不良信息举报电话:022-22558618 举报邮箱:dljd@tidljd.com