LeetCode 题解:22. 括号生成,递归先生成再过滤,JavaScript,详细注释

用户头像
Lee Chen
关注
发布于: 2020 年 10 月 17 日
LeetCode题解:22. 括号生成,递归先生成再过滤,JavaScript,详细注释

原题链接:https://leetcode-cn.com/problems/generate-parentheses/



解题思路:



  1. 先用递归生成所有可能的括号。

  2. 每层递归都对应左右括号两种可能,同时统计当前生成的字符串长度。

  3. 生成完相应长度的字符串后,过滤出有效括号,并将其存入结果。



// 校验字符串是否合法
function isValid(str) {
let count = 0; // 使用变量计数判断是否有成对括号
// 遍历所有字符
for (const char of str) {
// 遇到左括号时,统计数量
if (char === '(') {
count++;
} else {
// 遇到右括号时,如果左括号数量为0,表示括号不成对
if (!count) {
return false;
}
// 遇到右括号时,如果左括号有计数,则抵消一个
count--;
}
}
// 若完成遍历时,计数为0,表示括号都成对
return !count;
}
// 递归生成所有可能的字符串
function generate(str, max, result) {
// 递归终止条件:
// 1. 生成的字符串达到最大值
if (str.length === max) {
// 2. 校验括号是否合法
if (isValid(str)) {
// 将合法的括号存入结果
result.push(str);
}
// 生成的字符串已达到最大长度时,退出循环
return;
}
// 当前层逻辑
// 当前生成字符串有左右括号两种可能性
let str1 = str + '(';
let str2 = str + ')';
// 进入下一层递归
generate(str1, max, result);
generate(str2, max, result);
}
/**
* @param {number} n
* @return {string[]}
*/
var generateParenthesis = function (n) {
let result = []; // 存储结果
// 递归生成所有可能括号,再过滤出合法的括号
generate(
'', // 初始字符串为空
n * 2, // 生成的字符串长度
result, // 存储结果
);
return result; // 返回结果
};



发布于: 2020 年 10 月 17 日 阅读数: 9
用户头像

Lee Chen

关注

还未添加个人签名 2018.08.29 加入

还未添加个人简介

评论

发布
暂无评论
LeetCode题解:22. 括号生成,递归先生成再过滤,JavaScript,详细注释