leetcode 22 括号生成
文章目录
22. 括号生成
数字 n 代表生成括号的对数,请你设计一个函数,用于能够生成所有可能的并且 有效的 括号组合。
输入:n = 3
输出:["((()))","(()())","(())()","()(())","()()()"]
暴力1思路
- 给定n,所以合法的括号包含n个左括号和n个右括号。每次选择增加左/右,剩下的字符串与原问题相同
- 左括号>n / 右括号 > n / 右括号 > 左括号 这些情况均不合法,用于剪枝
class Solution {
public:
vector<string> res;
vector<string> generateParenthesis(int n) {
dfs(n, "", 0, 0);
return res;
}
void dfs (int n, string cur, int lc, int rc) {
if (lc > n || rc > n || rc > lc) {
return;
}
if (lc == n && rc == n) {
res.push_back(cur);
return;
}
dfs(n, cur + "(", lc + 1, rc);
dfs(n, cur + ")", lc, rc + 1);
}
};dp 思路
- n的括号,可以由小于n的括号推导出
从n-1到n,增加了一对括号。
- 这一对括号要么在原有括号外侧;( 原来 )
- 这一对括号要么在原有括号右侧;原来 ()
也就是实际结果等于
- ( i=p的括号 ) + i=q的括号
- p+q = n-1
class Solution {
public:
vector<string> generateParenthesis(int n) {
if (n == 0) {
return {};
}
if (n == 1) {
return {"()"};
}
vector<vector<string>> dp(n+1);
dp[0] = {""};
dp[1] = {"()"};
for (int i = 2; i <= n; i++) {
for (int j = 0; j < i; j++) {
for (string p : dp[j]) {
for (string q : dp[i-j-1]) {
string cur = "(" + p + ")" + q;
dp[i].push_back(cur);
}
}
}
}
return dp[n];
}
};
评论
登录后参与技术讨论,分享你的经验与见解。
登录 / 注册暂无评论