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:
"((()))", "(()())", "(())()", "()(())", "()()()"
A:
--------------Recursively call 产生各种情况,同时检测是否正确-------------------
----------------------3 rd Pass. ----------------------
最新的思路是这样的 : 3 = (2)[即单独3] or 2+1 or 1+2 or 1+1+1
对每个n , 可以写成的加和的方式为f(n)
则f(n) = ( f(n-1) ) (f(n-1)外边加括号
+ f(i) * f(n-i) i = 1,2....n-1
头脑不清晰,先用试错的方法先写完的。
public class Solution { public ArrayList<String> generateParenthesis(int n) { ArrayList<String> al = new ArrayList<String>(); int nLeft = 1, nRight = 0; getBrace("(", nLeft,nRight,n,al); return al; } private void getBrace(String str, int nLeft,int nRight,int n,ArrayList<String> al){ if(nLeft < nRight || nRight>n || nLeft>n) return; if(nLeft == nRight && nLeft == n) al.add(str); getBrace(str+"(", nLeft+1,nRight,n, al); getBrace(str+")", nLeft,nRight+1,n , al); } }
用char Array,save more space
public class Solution { public List<String> generateParenthesis(int n) { char[] A = new char[n+n]; List<String> list = new LinkedList(); dfs(A,list,n,n); return list; } private void dfs(char[] A, List<String> list, int nLeft, int nRight){ if(nLeft > nRight || nLeft<0 || nRight<0) return; if(nLeft ==0 && nRight ==0){ list.add(new String(A)); return; } int i = A.length - nLeft-nRight; A[i] = '('; dfs(A,list,nLeft-1,nRight); A[i] = ')'; dfs(A,list,nLeft, nRight-1); } }
-------------Iterative call -----------------但是思想跟recursive一样, 用了stack保存----------------
public class Solution { public List<String> generateParenthesis(int n) { List<String> list = new LinkedList(); List<String> queue = new LinkedList(); List<int[]> queue2 = new LinkedList(); queue.add(""); int[] arr = new int[2]; queue2.add(arr); while(!queue.isEmpty()){ String str = queue.remove(0); // pull int[] A = queue2.remove(0); int leftUsed = A[0], rightUsed = A[1]; if(leftUsed >n || rightUsed > n || leftUsed < rightUsed) continue; if(leftUsed == n && rightUsed == n) list.add(str); queue.add(str+"("); int[] left2 = {leftUsed+1,rightUsed}; queue2.add(left2); queue.add(str+")"); int[] right2 = {leftUsed,rightUsed+1}; queue2.add(right2); } return list; } }
就是 递归,将 n 简化为n-1 ------------这个思路不对。
"((()))", "(()())", "(())()", "()(())", "()()()"
0 = ""
1= "()"
2 = 1+1
2 = 2
3 = 1 + 1 + 1
3 = 1 + 2 --------------->2 is ( 1 )
3 = 2 + 1
3 = 3 ---> 最外面的一个paranthesis中包含了( 2 )
----------------就是先加入一个,然后递归调用,先前的,基于递归效率不高, 想用DP算法的方法,没有搞定。
这个题目最终的结果数目是 Catalan number
http://en.wikipedia.org/wiki/Catalan_number
---------------第二遍---------- DP 方法-------- ------
对于第一遍所遇到的, duplicate的问题, 我们用了 Set 来解决。
public class Solution { public ArrayList<String> generateParenthesis(int n) { // DP , pre-calculated list are in all ArrayList<ArrayList<String>> all = new ArrayList<ArrayList<String>>(); ArrayList<String> al = new ArrayList<String>(); al.add("()"); all.add(al);// add the case when n ==1, coz we do not want the for (int i = 1; i < n; i++) { al = new ArrayList<String>(); ArrayList<String> preAl = all.get(i - 1); for (int j = 0; j < preAl.size(); j++) al.add("(" + preAl.get(j) + ")"); // add other combinations for (int j = 0; j < i; j++) { int k = i - j - 1;// minus 1 , coz i,j are index, ArrayList<String> left = all.get(j); ArrayList<String> right = all.get(k); for (int jj = 0; jj < left.size(); jj++) for (int kk = 0; kk < right.size(); kk++) al.add(left.get(jj) + right.get(kk)); } // remove duplicates HashSet<String> set = new HashSet<String>(); set.addAll(al); al.clear(); al.addAll(set); all.add(al); } return all.get(n - 1); } }
Mistakes:
1: 递归的时候,开始仅仅假设了两种情况
()+oneLess
( + oneLess + )
还有一种情况,就是 ()加在后边 (这时候,有可能有重复,)
2: n ==4 ---》 有一种情况, 是(())(()) 是不能分成 n ==3 的情况的。 思路不对啊。应该是2+2 (基于DP的 一个个加上来的 算法)
Learned:
No comments:
Post a Comment