LeetCode 0022 - Generate Parentheses
# Hints
- DFS
# 题面
Difficulty | Time Complexity Limit | Extra-Memory Complexity Limit |
---|---|---|
Medium | or |
Given pairs of parentheses, write a function to generate all combinations of well-formed parentheses.
For example, given , a solution set is:
[
"((()))",
"(()())",
"(())()",
"()(())",
"()()()"
]
# 题意
给定一个正整数 ,求 对括号的所有合法的排列组合,即所有长为 的合法的括号匹配字符串。
# 题解
可以暴力枚举所有可能的 种排列,然后判断每种排列是否合法,时间复杂度为 。
但这显然不是最优解,因为对于本题而言,如果用DFS实现,我们可以进行合法性判断的剪枝,只需要在DFS的过程中统计当前左右括号个数即可。
我们知道 对括号匹配的合法排列数为第 项卡特兰数 ,因此DFS的时间复杂度为 。
# AC代码
class Solution {
public:
vector<string> generateParenthesis(int n) {
// DFS
vector<string> res;
string str = "";
dfs(0, 0, 0, n, str, res);
// 返回
return res;
}
// 深度优先搜索
void dfs(int depth, int lcnt, int rcnt, const int n, string & str, vector<string> & res) {
// 递归终止
if (depth == 2 * n) {
res.push_back(str);
return;
}
// 递归左括号
if (lcnt < n) {
str += '(';
dfs(depth + 1, lcnt + 1, rcnt, n, str, res);
str.pop_back();
}
// 递归右括号
if (rcnt < lcnt) {
str += ')';
dfs(depth + 1, lcnt, rcnt + 1, n, str, res);
str.pop_back();
}
}
};
- 01
- Reading Papers - Kernel Concurrency06-01
- 02
- Linux Kernel - Source Code Overview05-01
- 03
- Linux Kernel - Per-CPU Storage05-01