class Solution {
bool check(string u){
int l = 0;
for(int i = 0;i < u.length();i++){
if(u[i] == '(') l ++;
else l --;
if(l < 0) return false;
}
return !l;
}
public:
vector<string> generateParenthesis(int n) {
string u;
vector<string> res;
for(int i = 0;i < n;i++) u += "()";
sort(u.begin(),u.end());
do{
if(check(u)) res.push_back(u);
}while(next_permutation(u.begin(),u.end()));
return res;
}
};
这道题可以通过借助next_permutation
函数和括号合法性检测来实现。
这是我优化后的写法。
题目中n的最大取值为8,但采用无剪枝的递归仍会超时。
如下代码所示。
超时代码
class Solution {
private:
vector<string> res;
int n;
void insertParenthesis(string u){
if(u.length() / 2 == n){
bool exist = false;
for(auto it : res){
if(it == u){
exist = true;
break;
}
}
if(!exist) res.push_back(u);
return;
}
for(int i = 0;i < u.length() + 1;i++){
string v = u.substr(0,i) + "()" + u.substr(i);
insertParenthesis(v);
}
}
public:
vector<string> generateParenthesis(int n) {
this->n = n;
insertParenthesis("");
return res;
}
};
经过计算,该代码在最大规模的情况时计算次数约为 34459425 34459425 34459425次,而第一份代码的计算次数为 8 ! = 40320 8! = 40320 8!=40320次左右。因此实际时间复杂度相差了约1000倍。
题目链接
原创不易,感谢支持!