Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses.
For example, given n = 3, a solution set is:
"((()))", "(()())", "(())()", "()(())", "()()()"
这道题我是用递归的方式做的,用堆栈来判断是否复合条件,同时加上一个判断有多少左括号的函数。
网上有人有个更优美而且更好理解的方法。
For example, given n = 3, a solution set is:
"((()))", "(()())", "(())()", "()(())", "()()()"
这道题我是用递归的方式做的,用堆栈来判断是否复合条件,同时加上一个判断有多少左括号的函数。
public class Solution { public boolean isValid(String s) { boolean result = false; if (s == null || s.length() < 2) { return false; } Stack<Character> st = new Stack<Character>(); for (int i = 0; i < s.length(); i++) { if (s.charAt(i) == '('||s.charAt(i) == ')') { if (st.isEmpty()) { st.push(s.charAt(i)); } else { if ((char) st.peek() + s.charAt(i) == 81 ) { st.pop(); } else { st.push(s.charAt(i)); } } } } if (st.isEmpty()) { result = true; } else { result = false; } return result; } public List<String> generateParenthesis(int n) { List<String> result = generateParentheMax(n*2,n); return result; } public List<String> generateParentheMax(int n,int num) { if (n < 1) { return new ArrayList<String>(); } List<String> ls = null; List<String> result = new ArrayList<String>(); if (n > 1) { ls = generateParentheMax(n-1,num); for (String st : ls) { if (isValid(st)) { String s1 = st + "("; result.add(s1); } else { String s = st + ")"; result.add(s); if(findCharSumInString(st, '(')<num){ String s1 = st + "("; result.add(s1); } } } } else { String s2 ="("; result.add(s2); } return result; } private int findCharSumInString(String s, char c) { int sum = 0; if (null == s || s.length() == 0) { return sum; } for (int i = 0; i < s.length(); i++) { if (c == s.charAt(i)) { sum++; } } return sum; } }
网上有人有个更优美而且更好理解的方法。
public class Solution { public List<String> generateParenthesis(int n) { ArrayList<String> result = new ArrayList<String>(); ArrayList<Integer> diff = new ArrayList<Integer>(); result.add(""); diff.add(0); for (int i = 0; i < 2 * n; i++) { ArrayList<String> temp1 = new ArrayList<String>(); ArrayList<Integer> temp2 = new ArrayList<Integer>(); for (int j = 0; j < result.size(); j++) { String s = result.get(j); int k = diff.get(j); if (i < 2 * n - 1) { temp1.add(s + "("); temp2.add(k + 1); } if (k > 0 && i < 2 * n - 1 || k == 1 && i == 2 * n - 1) { temp1.add(s + ")"); temp2.add(k - 1); } } result = new ArrayList<String>(temp1); diff = new ArrayList<Integer>(temp2); } return result; } }
发表评论
-
Merge k Sorted Lists
2015-03-12 19:55 325Merge k sorted linked lists and ... -
Generate Parentheses
2015-03-05 22:39 0Given n pairs of parentheses, w ... -
Valid Parentheses
2015-03-05 22:33 307Given a string containing just ... -
Remove Nth Node From End of List
2015-03-05 22:31 339Given a linked list, remove the ... -
Letter Combinations of a Phone Number
2015-03-05 22:30 330Letter Combinations of a Phone ... -
4Sum
2015-03-05 22:26 311Given an array S of n integers, ... -
3Sum Closest
2015-03-05 22:25 291Given an array S of n integers, ... -
3Sum
2015-03-03 22:34 317Given an array S of n integers, ... -
Longest Common Prefix
2015-03-03 22:21 327Write a function to find the lo ... -
Roman to Integer
2015-03-03 22:20 326Given a roman numeral, convert ... -
Integer to Roman
2015-03-01 23:35 289Given an integer, convert it to ... -
Container With Most Water
2015-03-01 22:55 321Given n non-negative integers a ... -
Regular Expression Matching
2015-03-01 20:19 366Implement regular expression ma ... -
Palindrome Number
2015-02-13 22:08 330Determine whether an integer is ... -
String to Integer (atoi)
2015-02-13 11:07 341Implement atoi to convert a str ... -
Reverse Integer
2015-02-12 23:39 227Reverse digits of an integer. ... -
ZigZag Conversion
2015-02-12 23:37 254The string "PAYPALISHIRING ... -
Longest Palindromic Substring
2015-02-12 22:50 334Given a string S, find the long ... -
Add Two Numbers
2015-02-12 22:12 300You are given two linked lists ... -
Longest Substring Without Repeating Characters
2015-02-11 21:14 425[size=24px;]Longest Substring W ...
相关推荐
第四章 Leetcode 题解 1. Two Sum 2. Add Two Numbers 3. Longest Substring Without ...22. Generate Parentheses 23. Merge k Sorted Lists 24. Swap Nodes in Pairs 25. Reverse Nodes in k-Group 26. Remove Dupli
237 Generate Parentheses 575 238 Combination Sum 577 239 Combination Sum II 579 240 Combination Sum III 581 241 Combinations 583 242 Letter Combinations of a Phone Number 587 243 Restore IP Addresses ...
Generate Parentheses Sudoku Solver Word Search 总结 分治法 Pow(x,n) Sqrt(x) 贪心法 Jump Game Jump Game II Best Time to Buy and Sell Stock Best Time to Buy and Sell Stock II Longest Substring Without ...
leetcode 530 ** LeetCode 题目更新 ** 用来记录业余时间所做的算法题目,保持对于数据结构的熟悉。 ** Leetcode 题目列表 ...Parentheses ...Generate Parentheses 028 Implement strStr() 031 Next Permutat
lru缓存leetcode leetcode 1. Two Sum 2. Add Two ...Generate Parentheses 25. Reverse Nodes in k-Group 26. Remove Duplicates from Sorted Array 27. Remove Element 28. Implement strStr() 3
Parentheses | ImplementstrStr.java //28. Implement strStr() │ LongestIncreasingSubsequence.java 300.Longest Increasing Subsequence | LongestPalindromicSubstring.java 5. Longest Palindromic Substring...
leetcode 2 LeetCode-练习 我的 ...Generate Parentheses 运行时间:164 毫秒内存使用:22.5 MB 26. Remove Duplicates from Sorted Array 运行时间:100 毫秒内存使用:15.2 MB 27. Remove Element
Generate Parentheses 18 3 sum 扩展版, 外层多套一个循环即可。注意判断重复及细节优化 19 细节:nodelist前插入一个dummy node. 删除倒数第n 等于正数查到len - n 20 用stack 最后stack应该是空的 21 遍历直到二...
generate-parentheses【】【中等】 这是一道递归题目,想法很重要,保证括号合法性是另一个要点 private List result; public List generateParenthesis(int n) { result = new ArrayList(); _generate(0, 0, n, "")...
022_Generate_Parentheses 023_Merge_k_Sorted_Lists 024_Swap_Nodes_in_Pairs 025_Reverse_Nodes_in_k-Group 026_Remove_Duplicates_from_Sorted_Array 027_Remove_Element 028_Implement_strStr() 029_...
题目来源:https://leetcode-cn.com/problems/generate-parentheses/submissions/ 题目 给出 n 代表生成括号的对数,请你写出一个函数,使其能够生成所有可能的并且有效的括号组合。 例如,给出 n = 3,生成结果为...
leetcode 答案LeetCode 算法的复杂度分析。...因为是递回求解,所以很抽象不好懂,这里以leetcode的generate-parentheses一道题目为例,给定n,要找出n个括号的各种组合,例如n=2 ,答案会是[(()), ()()]
parentheses regardless of whether we are returning a value or whether we are using the Call statement. It makes the code much more readable and is a new standard for VB programmers that is consistent ...
Advanced Bash-Scripting Guide 高级Bash脚本编程指南>> 一本深入学习shell脚本艺术的书籍 非常好的书 强烈推荐 附有超多实例 Advanced Bash-Scripting Guide.......................................................