[LeetCode] 022. Generate Parentheses (Medium) (C++/Java/Python)

正文概述

索引：[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

题意：

产生有 n 对括号的所有有效字符串。

分析：

用 DFS 可以很快做出来，能加’(‘就加’(‘，能加’)’就加’)’。（下面的 C++ 实现）
还有很机灵方法写出很短的 DFS 。 (Java 实现)
对 DFS 都可以进行记忆化，用空间换时间。 (Python 实现)

代码：

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, pos + 1, n, used);
tmp.pop_back();
}
}

public:
vector<string> generateParenthesis(int n) {
vector<string> res;
if (n == 0)
return res;
tmp = "";
dfs(res, 0, n, 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)

索引

波比源码 – 精品源码模版分享 | www.bobi11.com
1. 本站所有资源来源于用户上传和网络，如有侵权请邮件联系站长！
2. 分享目的仅供大家学习和交流，您必须在下载后24小时内删除！
3. 不得使用于非法商业用途，不得违反国家法律。否则后果自负！
4. 本站提供的源码、模板、插件等等其他资源，都不包含技术服务请大家谅解！
5. 如有链接无法下载、失效或广告，请联系管理员处理！
6. 本站资源售价只是赞助，收取费用仅维持本站的日常运营所需！
7. 本站源码并不保证全部能正常使用，仅供有技术基础的人学习研究，请谨慎下载
8. 如遇到加密压缩包，请使用WINRAR解压,如遇到无法解压的请联系管理员！

波比源码 » [LeetCode] 022. Generate Parentheses (Medium) (C++/Java/Python)

分享到：