题解 |找到规律后的简单做法
括号生成
http://www.nowcoder.com/practice/c9addb265cdf4cdd92c092c655d164ca
看了一圈好像没有用我这个方法的，感觉实现起来很方便
核心是抓住 一个合法序列插入另一个合法序列任意位置仍然合法 这条性质
那么规模为n的问题 转化为 对规模为n-1的问题插入一对新括号的问题
给出JAVA实现如下
public ArrayList<String> generateParenthesis (int n) {
ArrayList<String> arr=new ArrayList<>();
if(n==0) return null;
// write code here
//合法括号 不以)开头，不以(结尾
//即()开头结尾
//消去几个（）后，仍应该保持这个性质,比如())不行
//一个合法序列插入另一个合法序列任意位置仍然合法
//问题转化成，从一个括号开始，用其他括号慢慢插
String init="()";
if(n==1){
arr.add(init);
return arr;
}
HashSet<String> set=new HashSet<>();
ArrayList<String> lastRes=generateParenthesis(n-1);
for(String item:lastRes){
//可插入空位个数枚举,2(n-1)+1=2n-1
for(int i=0;i<2*n-1;i++){
String prefix;
if(i==0) prefix="";
else prefix=item.substring(0,i);
String end;
if(i==2*n-2) end="";
else end=item.substring(i);
set.add(prefix+"()"+end);
}
}
for(Iterator<String> it=set.iterator();it.hasNext();){
arr.add(it.next());
}
return arr;
}
