https://leetcode-cn.com/problems/generate-parentheses/
我的方法一:动态规划+哈希表
步骤
- 给出n
- 从1开始,1是(),2是分别在()的左、中、右插入(),并去重
- 即f(n) 是在f(n-1)的最左到最右边位置插入(),并去重
- 去重利用哈希表
初始条件和边界条件
- n=0,返回""
- n=1,返回"()"
复杂度
时间复杂度:O(n!)
空间复杂度:O(n!)
代码
class Solution {
public:
vector<string> generateParenthesis(int n) {
if(n == 0){
return vector<string>();
}
unordered_set<string> s;
vector<string> ret1;
ret1.push_back("()");
vector<string> ret2;
string combine;
vector<string>* ret_tmp1 = 0;
vector<string>* ret_tmp2 = 0;
for(int i = 1; i<n; i++){
if(ret1.size() > 0){
ret_tmp1 = &ret1;
ret_tmp2 = &ret2;
}else{
ret_tmp1 = &ret2;
ret_tmp2 = &ret1;
}
for(auto & itor : *ret_tmp1){
for(int j = 0; j<=itor.size(); j++){
combine = string(itor.c_str(), j) + "()" + string(itor.c_str()+j, itor.size() - j);
if(s.find(combine) == s.end()){
ret_tmp2->push_back(combine);
s.insert(combine);
}
}
}
ret_tmp1->clear();
}
if(ret1.size() > 0){
return ret1;
}else{
return ret2;
}
}
};
网友评论