Solution to LeetCode Generate Parenthesis question.
There are two solutions I can think of: one based on the BNF representation, and one based on counting how many parenthesis we have left.
The detailed explanation can be found here and here
The following Java code uses the BNF approach:
/* grammar:
expr := e
expr := '(' expr ')' expr
*/
public ArrayList<String> generateParenthesis(int n) {
return generateParenthesis(n, new HashMap<Integer,ArrayList<String>>());
}
private ArrayList<String> generateParenthesis(int n, HashMap<Integer,ArrayList<String>> hm){
if(hm.containsKey(n)) return hm.get(n);
ArrayList<String> result = new ArrayList<String>();
if(n == 0) result.add("");
for(int i = 0; i < n; i++){
ArrayList<String> leftExpr = generateParenthesis(i,hm);
ArrayList<String> rightExpr = generateParenthesis(n-i-1,hm);
for(String s1 : leftExpr){
for(String s2 : rightExpr){
result.add("(" + s1 + ")" + s2);
}
}
}
hm.put(n,result);
return result;
}