【LeetCode每日一题】22. Generate Parentheses
题目描述
Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses.
For example, given n = 3, a solution set is:
[
"((()))",
"(()())",
"(())()",
"()(())",
"()()()"
]数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且 有效的 括号组合。
题解
暴力破解
- 生成所有可能的括号组合；
- 针对每一种组合，判断是否有效：有效，保留；无效，舍弃。
- 有效性验证：左括号开始，能形成括号对。
解法：
class Solution {
public:
vector<string> generateParenthesis(int n) {
vector<string> result;
if (n < 0) return result;
generateAll(n, 0, "", result);
return result;
}
private:
void generateAll(int n, int pos, string temp, vector<string> &res){
if (pos == 2 * n){
if(valid(temp)){
res.push_back(temp);
}
}
else{
temp += '(';
generateAll(n, pos+1, temp, res);
temp.pop_back();
temp += ')';
generateAll(n, pos+1, temp, res);
}
}
bool valid(string temp){
int balance = 0;
for (auto c: temp){
if (c == '(') balance += 1;
else balance -= 1;
if (balance < 0) return false;
}
return balance == 0;
}
};缺点是：时间复杂度太大。
bfs/递归法
在生成过程中进行剪枝，及时舍弃无效的情况：
- 使用两个变量left、right，分别表示生成括号对中的仍然需要的括号数量，生成过程中，left <= right；如果出现left > right，说明生成的括号对无效，舍弃即可；
- 注意，递归结束条件，一种是生成字符对无效，另一种是生成最终的结果对。
代码：
class Solution {
public:
vector<string> generateParenthesis(int n) {
vector<string> result;
if (n < 0) return result;
helper(n, n, "", result);
return result;
}
private:
void helper(int left, int right, string tmp, vector<string> &res){
if (left < 0 || right < 0 || left > right) return;
if (left == 0 && right == 0){
res.push_back(tmp);
return;
}
helper(left-1, right, tmp+'(', res);
helper(left, right-1, tmp+')', res);
}
};举报
腾讯云开发者
