Generate Parentheses
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:
"((()))", "(()())", "(())()", "()(())", "()()()"
public class Solution {
public ArrayList<String> generateParenthesis(int n) {
// Start typing your Java solution below
// DO NOT write main() function
ArrayList<String> res = new ArrayList<String>();
ArrayList<Integer> diff = new ArrayList<Integer>();
res.add("");
diff.add(0);
for(int i=0;i<2*n;i++){
ArrayList<String> temp1 = new ArrayList<String>();
ArrayList<Integer> temp2 = new ArrayList<Integer>();
for(int j=0;j<res.size();j++){
String s = res.get(j);
int k = diff.get(j);
if(i<2*n-1){
temp1.add(s+"(");
temp2.add(k+1);
}
if(k>0 && i<2*n-1 || k==1 && i==2*n-1){
temp1.add(s+")");
temp2.add(k-1);
}
}
res = new ArrayList<String>(temp1);
diff = new ArrayList<Integer>(temp2);
}
return res;
}
}
1 comment:
Only a bit improvement, we don't need to allocate new objects at the end of the loop. Just put it like this:
res = temp1;
diff = temp2;
Post a Comment