leetcode 22. Generate Parentheses 谷歌面试题
本帖最后由 Seawolf 于 2019-8-17 14:21 编辑这是一道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);
}
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 上升的不少。
学习一下，补充知识
页:
[1]