leetcode 22. Generate Parentheses 谷歌面试题

Seawolf

这是一道Google的面试题

1. Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses.
   
2. 
   
3. For example, given n = 3, a solution set is:
   
4. 
   
5. [
   
6.   "((()))",
   
7.   "(()())",
   
8.   "(())()",
   
9.   "()(())",
   
10.   "()()()"
    
11. ]

复制代码

首先想到的是用hashset 来解决这个问题

1. import java.util.*;
   
2. 
   
3. public class Solution {
   
4.        
   
5.         HashSet<String> solutionHashSet;
   
6.        
   
7.         public List<String> generateParenthesis(int n){
   
8.                
   
9.                 solutionHashSet = new HashSet<>();
   
10.                
    
11.                 generateParenthesis("", n, n);
    
12.                
    
13.                 Object[] o = solutionHashSet.toArray();
    
14.                 List solutionSet = new ArrayList();
    
15.                
    
16.                 for(int i = 0; i< o.length; i++) {
    
17.                        
    
18.                         solutionSet.add(o[i]);
    
19.                 }
    
20.                
    
21.                 return solutionSet;
    
22.         }
    
23.        
    
24.         public void generateParenthesis(String s, int o, int c) {
    
25.                
    
26.                 if(o == 0 && c == 0) {
    
27.                        
    
28.                         solutionHashSet.add(s);
    
29.                         return;
    
30.                 }
    
31.                
    
32.                 if(o == 0) {
    
33.                        
    
34.                         generateParenthesis(s+ ")", o , c-1);
    
35.                 }
    
36.                
    
37.                 if( c< 0 || o < 0 || o > c) {
    
38.                        
    
39.                         return;
    
40.                 }
    
41.                
    
42.                 if(c == 0) {
    
43.                        
    
44.                         generateParenthesis(s+ "(", o -1 , c);
    
45.                 }
    
46.                
    
47.                 if(o < c) {
    
48.                        
    
49.                         generateParenthesis(s+ "(", o -1 , c);
    
50.                         generateParenthesis(s+ ")", o , c-1);
    
51.                 }
    
52.                
    
53.         }
    
54. 
    
55. }
    
56. 
    

复制代码

但是这个code的efficiency 太差了，需要改进

1. import java.util.*;
   
2. 
   
3. class Solution {
   
4. 
   
5.    
   
6.     public void dfs(int left, int right, String str, ArrayList array) {
   
7.            
   
8.             if(left == 0 && right == 0) {
   
9.                    
   
10.                     array.add(str);
    
11.                 return;
    
12.             }
    
13.             
    
14.             if(left < right) {
    
15.                    
    
16.                     dfs(left, right-1, str + ")",array);
    
17.             }
    
18.             
    
19.             if(left >0) {
    
20.                    
    
21.                     dfs(left-1,right,str+"(",array);
    
22.             }
    
23.             
    
24.         }
    
25. 
    
26.     public ArrayList<String> generateParenthesis(int n) {
    
27.         
    
28.         ArrayList<String> result = new ArrayList<String>();
    
29.         
    
30.         String re = "";
    
31.         
    
32.         dfs(n,n,re,result);
    
33.         
    
34.         return result;
    
35.         
    
36.     }
    
37. }

复制代码

修改以后的efficiency 上升的不少。

zjaccc

学习一下，补充知识