国内最全IT社区平台 联系我们 | 收藏本站
华晨云阿里云优惠2
您当前位置:首页 > php开源 > php教程 > [LeetCode] 022. Generate Parentheses (Medium) (C++/Java/Python)

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

来源:程序员人生   发布时间:2015-03-14 09:07:50 阅读次数:3683次

索引:[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 对括号的所有有效字符串。

分析

  1. 用 DFS 可以很快做出来,能加’(‘就加’(‘,能加’)’就加’)’。(下面的 C++ 实现)
  2. 还有很机灵方法写出很短的 DFS 。 (Java 实现)
  3. 对 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)


生活不易,码农辛苦
如果您觉得本网站对您的学习有所帮助,可以手机扫描二维码进行捐赠
程序员人生
------分隔线----------------------------
分享到:
------分隔线----------------------------
关闭
程序员人生