https://leetcode-cn.com/problems/generate-parentheses/submissions/
使用递归+双层循环的方式来解决。主要思路是将当前状态中所有可以成对的可能性都考虑到,先考虑左括号,再考虑右括号。然后让每种可能性都递归下去。
代码还有 bug(因为结果会产生许多长度不满足的数组),不过已经可以 Accept 了,而且只击败了 24% 的人。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 class Solution { public List<String> ret; public void gp (int n, int l, int r, String nowStr) { if (l==n && r==n){ if (nowStr.length()==n*2 ) ret.add(nowStr); } String ts1=nowStr; while (l<n){ l++; String ts2=ts1+"(" ; gp(n,l,r,ts2); while (r<l){ r++; ts2=ts2+")" ; gp(n,l,r,ts2); } } } public List<String> generateParenthesis (int n) { ret=new ArrayList<>(); gp(n,0 ,0 ,"" ); return ret; } }
经过检查,是因为 Java 的字符串赋值是传递地址的,必须使用传递值才可以。所以有了如下的方案,但是因为会出现重复结果,所以使用了 HashSet 转 ArrayList。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 class Solution { public Set<String> res; public void gp (int n, int l, int r, String nowStr) { if (l==n && r==n) res.add(nowStr); while (l++<n){ nowStr+="(" ; gp(n,l,r,nowStr); String ts=new String(nowStr); int tr=r; while (tr++<l){ ts=ts+")" ; gp(n,l,tr,ts); } } } public List<String> generateParenthesis (int n) { res=new HashSet<>(); gp(n,0 ,0 ,"" ); return new ArrayList<String>(res); } }
但发现速度更慢了,只击败了 4%的人。原因应该是数组的重复复制以及 hashset 去重。
看了一下 Solutions 中的答案,发现方法二 Backtracking(回溯算法)和我之前的很像,不过我在一次递归中考虑的太多,导致重复。
所以,在回溯里只要考虑下一步做什么就可以了,不要考虑这么多。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 class Solution { public List<String> res; public void gp (int n, int l, int r, String nowStr) { if (nowStr.length()==n*2 ){ res.add(nowStr); return ; } if (l<n){ gp(n,l+1 ,r,nowStr+"(" ); } if (r<l){ gp(n,l,r+1 ,nowStr+")" ); } } public List<String> generateParenthesis (int n) { res=new ArrayList<>(); gp(n,0 ,0 ,"" ); return res; } }
最后, solution 给出了一个最简单的方法。可以构成成堆的括号的标准就是有一个东西把另外的东西括起来,所以以括号为单位进行递归是最方便的选择。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 class Solution { public List<String> generateParenthesis (int n) { List<String> ans = new ArrayList(); if (n == 0 ) { ans.add("" ); } else { for (int c = 0 ; c < n; ++c) for (String left: generateParenthesis(c)) for (String right: generateParenthesis(n-1 -c)) ans.add("(" + left + ")" + right); } return ans; } }
时间过去了快一年,这里是我现在的解法,同样是回溯法,但简洁了许多。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 class Solution {public : vector<string> generateParenthesis (int n) { vector<string> result; if (n<=0 ) return result; generate (result, "" , n, 0 ); return result; } void generate (vector<string>& result, string now, int nleft, int unpaired) { if (nleft==0 && unpaired==0 ) { result.push_back (now); return ; } if (nleft!=0 ) generate (result, now+'(' , nleft-1 , unpaired+1 ); if (unpaired!=0 ) generate (result, now+')' , nleft, unpaired-1 ); } };