[LeetCode] 022. Generate Parentheses (Medium) (C++/Java/Pyth
发布时间：2020-12-13 20:15:59 所属栏目：PHP教程 来源：网络整理
导读：索引：[LeetCode] Leetcode 题解索引 (C/Java/Python/Sql) Github: https://github.com/illuz/leetcode 022.Generate_Parentheses (Medium) 链接 ： 题目：https://oj.leetcode.com/problems/generate-parentheses/ 代码(github)：https://github.com/illuz/
|
索引：[LeetCode] Leetcode 题解索引 (C++/Java/Python/Sql) 022.Generate_Parentheses (Medium)链接：题目：https://oj.leetcode.com/problems/generate-parentheses/ 题意：产生有 n 对括号的所有有效字符串。 分析：
代码：C++: class Solution {
private:
string tmp;
void dfs(vector<string> &v,int pos,int n,int used) {
if (pos == n * 2) {
cout << tmp << endl;
v.push_back(tmp);
return;
}
if (used < n) {
tmp.push_back('(');
dfs(v,pos + 1,n,used + 1);
tmp.pop_back();
}
if (used * 2 > pos) {
tmp.push_back(')');
dfs(v,used);
tmp.pop_back();
}
}
public:
vector<string> generateParenthesis(int n) {
vector<string> res;
if (n == 0)
return res;
tmp = "";
dfs(res,0);
return res;
}
};
Java: public class Solution {
public List<String> generateParenthesis(int n) {
List<String> ret = new ArrayList<String>(),inner,outter;
if (n == 0) {
ret.add("");
return ret;
}
if (n == 1) {
ret.add("()");
return ret;
}
for (int i = 0; i < n; ++i) {
inner = generateParenthesis(i);
outter = generateParenthesis(n - i - 1);
for (int j = 0; j < inner.size(); ++j) {
for (int k = 0; k < outter.size(); ++k) {
ret.add("(" + inner.get(j) + ")" + outter.get(k));
}
}
}
return ret;
}
}
Python: class Solution:
# @param an integer
# @return a list of string
def generateParenthesis(self,n):
dp = {0: [""],1: ["()"]}
def memorial_dfs(n):
if n not in dp:
dp[n] = []
for i in range(n):
for inner in memorial_dfs(i):
for outter in memorial_dfs(n - i - 1):
dp[n].append('(' + inner + ')' + outter)
return dp[n]
return memorial_dfs(n)
（编辑：李大同） 【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容! |