BM60. [括号生成]
https://www.nowcoder.com/exam/oj?tab=%E7%AE%97%E6%B3%95%E7%AF%87&topicId=295
BM60. 括号生成
题目的主要信息：
- 求n对括号的全部合法组合，左右括号之间任意组合，只要合法就行
- 需要输出所有的结果
方法一：暴力构造+栈验证
具体做法：
首先构造一个"(((((((......))))))"形式的字符串，然后调用STL的next_permutation函数遍历其每一个排列组合，并验证其是否合法，如果合法则可以加入返回的vector中。
验证合法时，使用辅助栈，遇到左括号则入栈，遇到右括号则弹出一个栈中内容，若是栈为空的时候遇到了右括号，则没有左括号来匹配，即非法。
class Solution {
public:
bool isValid(string str){ //验证括号是否合法
stack<char> s; //栈中只存左括号
for(int i = 0; i < str.length(); i++){
if(s.empty() && str[i]==')') //空栈遇到右括号，不合法
return false;
if(str[i] == ')') //遇到右括号弹出一个左括号
s.pop();
else
s.push(str[i]); //加入左括号
}
return true;
}
vector<string> generateParenthesis(int n) {
string str1(n, '(');
string str2(n, ')');
string str = str1 + str2; //将所有括号写入str
vector<string> strs;
do{
if(isValid(str)) //合法括号入vector
strs.push_back(str);
}while(next_permutation(str.begin(), str.end())); //生成下一排列组合
return strs;
}
};
复杂度分析：
- 时间复杂度：
，next_permutation是一个全排列，加上每次都验证2n长度的字符串
- 空间复杂度：
，辅助栈和构造字符串时使用的空间
方法二：递归+余量构造法
具体做法：
全部构造的方法，构造了很多不必要的字符串，导致运算量陡增，我们可以用余量构造法：
一开始左右括号数剩余都是n，总括号数剩余2n，构造一个就用掉一个相应的括号，只有在括号都有余量的时候才能继续构造，而右括号还需要限制在余量比左括号多的时候才能继续构造。
每次构造采用递归的方式，构造了括号，把相应的括号数量减1送入子问题中进行递归。
这种方法也叫枝剪法：���剪递归树多余的部分。
class Solution {
public:
void recursion(int left, int right, int count, string s, vector<string>& res){
if(count == 0){
res.push_back(s);
return;
}
else if(left > 0) //左边还可以放
recursion(left - 1, right, count - 1, s + "(", res);
if(right > left) //右边也可以
recursion(left, right - 1, count - 1, s + ")", res);
}
vector<string> generateParenthesis(int n) {
vector<string> res;
recursion(n, n, 2 * n, "", res); //左右括号及总括号数余量放入递归
return res;
}
};
复杂度分析：
- 时间复杂度：
，复杂度取决于有多少个合法括号组合，这是第n个卡特兰数，由
渐近界定的
- 空间复杂度：
投递美团等公司10个岗位