leetcode 22. Generate Parentheses 谷歌面试题

Seawolf

这是一道Google的面试题

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:

[
  "((()))",
  "(()())",
  "(())()",
  "()(())",
  "()()()"
]

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

import java.util.*;

public class Solution {
        
        HashSet<String> solutionHashSet;
        
        public List<String> generateParenthesis(int n){
                
                solutionHashSet = new HashSet<>();
                
                generateParenthesis("", n, n);
                
                Object[] o = solutionHashSet.toArray();
                List solutionSet = new ArrayList();
                
                for(int i = 0; i< o.length; i++) {
                        
                        solutionSet.add(o[i]);
                }
                
                return solutionSet;
        }
        
        public void generateParenthesis(String s, int o, int c) {
                
                if(o == 0 && c == 0) {
                        
                        solutionHashSet.add(s);
                        return;
                }
                
                if(o == 0) {
                        
                        generateParenthesis(s+ ")", o , c-1);
                }
                
                if( c< 0 || o < 0 || o > c) {
                        
                        return;
                }
                
                if(c == 0) {
                        
                        generateParenthesis(s+ "(", o -1 , c);
                }
                
                if(o < c) {
                        
                        generateParenthesis(s+ "(", o -1 , c);
                        generateParenthesis(s+ ")", o , c-1);
                }
                
        }

}

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

import java.util.*;

class Solution {

    
    public void dfs(int left, int right, String str, ArrayList array) {
            
            if(left == 0 && right == 0) {
                    
                    array.add(str);
                return;
            }
            
            if(left < right) {
                    
                    dfs(left, right-1, str + ")",array);
            }
            
            if(left >0) {
                    
                    dfs(left-1,right,str+"(",array);
            }
            
        }

    public ArrayList<String> generateParenthesis(int n) {
        
        ArrayList<String> result = new ArrayList<String>();
        
        String re = "";
        
        dfs(n,n,re,result);
        
        return result;
        
    }
}

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

zjaccc

学习一下，补充知识