22. 括号生成
链接:https://leetcode-cn.com/problems/generate-parentheses/
题目描述见链接内容。
思考
昨天做这道题,没思路,看了题解学习了
写代码一直没休息,写到眼睛疼想吐
图啥
解法1:成对匹配
把一对括号()
看做一个从整体,当n === 1
是,结果是[()]
,n === 2
时,对[()]
进行遍历,()
有三个位置可以插入,插入的结果是()()
、(())
、()()
,显然是有重复的结果,可以利用Set
来去重:
var generateParenthesis = function (n) {
if (n === 0) {
return [];
}
if (n === 1) {
return ['()'];
}
const set = new Set();
for (const str of generateParenthesis(n - 1)) {
for (let i = 0, len = str.length; i < len + 2; i++) {
set.add(str.slice(0, i + 1) + '()' + str.slice(i + 1, len));
}
}
return [...set];
};
解法2:递归
需要找到规律:
- 当剩下的左括号和右括号数量相同时,下一个位置必须是左括号(如果是右括号,这个右括号就没人和它匹配了)
- 当剩下的左括号数量小于右括号数量时,下一个位置可以是左括号也可以是右括号
- 当剩下的左括号数量大于右括号数量时,无法再匹配成对
根据这个规律,进行递归
var generateParenthesis = function (n) {
const res = [];
generate('', n, n, res);
return res;
};
function generate(str, left, right, res) {
if (left === 0 && right === 0) {
res.push(str);
return;
}
if (left === right) {
generate(str + '(', left - 1, right, res);
} else if (left < right) {
if (left > 0) {
generate(str + '(', left - 1, right, res);
}
generate(str + ')', left, right - 1, res);
}
}