LeetCode 22 Generate Parentheses
概述
https://leetcode.com/problems/generate-parentheses/
如何保证括号是合法的呢?
回溯法(利用双栈保证合法)
我这里是用两个 stack:
class Solution {
public:
int n;
vector<string> ans;
vector<string> generateParenthesis(int n) {
this->n = n;
vector<char> sa;
vector<char> sb;
backtrack(sa, sb, 0);
return ans;
}
void backtrack(vector<char>& sa, vector<char>& sb, int i) {
if (i == n && sb.empty()) {
string t(sa.begin(), sa.end());
ans.push_back(t);
return;
}
if (!sb.empty()) {
sb.pop_back();
sa.push_back(')');
backtrack(sa, sb, i);
sa.pop_back();
sb.push_back(')');
}
if (i < n) {
sa.push_back('(');
sb.push_back(')');
backtrack(sa, sb, i + 1);
sb.pop_back();
sa.pop_back();
}
}
};
由于回溯法的性质(执行完选择后回溯到执行前的状态),后面的那两个 if 的顺序无所谓。
回溯法(依靠剩余的左右括号个数判断是否合法)
如果剩余的右括号个数小于左括号个数,说明不合法。
class Solution {
public:
vector<string> ans;
vector<string> generateParenthesis(int n) {
vector<char> s;
backtrack(n, n, s);
return ans;
}
void backtrack(int l, int r, vector<char>& s) {
if (l == 0 && r == 0) {
string t(s.begin(), s.end());
ans.push_back(t);
return;
}
if (l > r) return;
if (l > 0) {
s.push_back('(');
backtrack(l-1, r, s);
s.pop_back();
}
if (r > 0) {
s.push_back(')');
backtrack(l, r-1, s);
s.pop_back();
}
}
};
关于时间复杂度:
对于 backtrack 函数,状态有三个,分别是 left, right, track,这三个变量的所有组合个数就是 backtrack 函数的状态个数(调用次数)。 left 和 right 的组合好办,他俩取值就是 0~n 嘛,组合起来也就 n^2 种而已;这个 track 的长度虽然取在 0~2n,但对于每一个长度,它还有指数级的括号组合,这个是不好算的。 说了这么多,就是想让大家知道这个算法的复杂度是指数级,而且不好算,这里就不具体展开了,是 4^n / sqrt(n),有兴趣的读者可以搜索一下「卡特兰数」相关的知识了解一下这个复杂度是怎么算的。