首页 > 代码库 > [LeetCode]22 Generate Parentheses
[LeetCode]22 Generate Parentheses
https://oj.leetcode.com/problems/generate-parentheses/
http://fisherlei.blogspot.com/2012/12/leetcode-generate-parentheses.html
public class Solution { public List<String> generateParenthesis(int n) { // Solution B: // return generateParenthesis_BruteForce(n); // Solution A: return generateParenthesis_Dynamic(n); } //////////////////////////////////////// // Solution A: Dynamic // public List<String> generateParenthesis_Dynamic(int n) { List<String> result = new ArrayList<>(); generate(n, 0, 0, "", result); return result; } private void generate(int n, int left, int right, String s, List<String> result) { if (right > left) return; // ) cannot be more than ( if (left == n && right == n) { // A valid result. result.add(s); return; } if (left == n) // right ‘)‘ is less than n { generate(n, left, right + 1, s + ")", result); return; } generate(n, left + 1, right, s + "(", result); // Add ( generate(n, left, right + 1, s + ")", result); // Add ) } //////////////////////////////////////// // Solution A: Brute Force // public List<String> generateParenthesis_BruteForce(int n) { if (n < 0) return null; // Invalid input if (n == 0) return Collections.<String> emptyList(); List<Set<String>> results = new ArrayList<>(n); results.add(Collections.<String> singleton("()")); // Result for 1; for (int i = 1 ; i < n ; i ++) { Set<String> curR = new HashSet<>(); Set<String> lastR = results.get(i - 1); for (String s : lastR) { // Add one more ‘(‘ in the begining; s = "(" + s; // Iterate s, Add ‘)‘ after each ‘(‘ for (int j = 0 ; j < s.length() ; j ++) { if (s.charAt(j) == ‘(‘) { String newStr = s.substring(0, j + 1) + ")" + s.substring(j + 1, s.length()); curR.add(newStr); } } } results.add(curR); } return new ArrayList<>(results.get(n - 1)); } }
[LeetCode]22 Generate Parentheses
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。