Tuesday, January 29, 2013

[leetcode] Generate Parentheses

Problem:
Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses.
For example:
n=1: "()"
n=2: "()()","(())"
n=3: "((()))","()(())","()()()","(()())","(())()"
...
While this problem seems familiar to me, I didn't have good solutions at first glance. Then my first step was to observe more examples and tried to find some patterns.

Let [n] indicates all well-formed combinations of number n. Then it was not difficult to find out that we had the following patters:
[n] = { "(" + [n-1] + ")"  , [1][n-1], [2][n-2], ...., [n-2][2], [n-1][1] }
where [m][n] indicates the cartesian product of two sets.
    e.g. [2][2] =  { "()()","(())" } x { "()()","(())" }
= { "()()()()","()()(())","(())()()","()()()()" }
As we can see, there will be duplicates of the product, so I use the Set container in java to avoid duplicates.

Then the main idea is to iterate from 1 to n. When calculate k, we can use the previous [1..k-1] results to generate the results of k.
public class GenerateParentheses {
  public ArrayList<String> generateParenthesis(int n) {
         
         ArrayList<Set<String>> list = new ArrayList<Set<String>>();
         
         int number=1;
         
         while (number<=n){
             Set<String> parentheses = new HashSet();
             //generate combinations of pattern "("+[number-1]+")"
             generateParentheses(number,list,parentheses);
             //generate combinations of pattern [1][number-1],[2][number-2],...[number-1][1]
             for(int i=1;i<number;i++){
                 int leftIndex=i-1;
                 int rightIndex=number-i-1;
                 for(String left:list.get(leftIndex)){
                     for(String right:list.get(rightIndex)){
                         parentheses.add(left+right);
                     }
                 }
             }
             //add results of this number and go on.
             list.add(parentheses);
             number++;
         }
         //add the elements to list required by OJ.
         ArrayList<String> result = new ArrayList<String>();
         Iterator<String> it = list.get(list.size()-1).iterator();
         while(it.hasNext())
            result.add(it.next());
         return result;
     }
     
     private void generateParentheses(int number,ArrayList<Set<String>> list,Set<String> parentheses){
         if(number==1){
             parentheses.add("()");
             return;
         }
         StringBuilder sb = new StringBuilder();
         for(String s:list.get(number-2)){
              sb.append("(");
              sb.append(s);
              sb.append(")");
              parentheses.add(sb.toString());
              sb.setLength(0);
         }
     }
}

I know...The code looks messy and kind of crazy with 4-nested loops.
After surfing online and discussed with others, I have a much better solution with the idea that is much easier to illustrate.

When the parameter is n, we are going to have n left parenthesis and n right parenthesis. We can add either "(" or ")" to current constructed string (initially empty string), but with some constrains:
1. No. of left parenthesis "(" much be less or equal to n.
2. Certainly, right parenthesis ")" need to be <= n, but also need to be <= no. of  "(".
Based this point, we can easily get a recursive approach :
public class GenerateParentheis {
 ArrayList<String> list;
    
    public ArrayList<String> generateParenthesis(int n) {
        list = new ArrayList<String>();
        generateParenthesis("",0,0,n);
        return list;
    }
    
    private void generateParenthesis(String s,int left,int right,int n){
        if(left==n && right==n){
            list.add(s);
            return;
        }
        if(left<n)
            generateParenthesis(s+"(",left+1,right,n);
        if(right<left)
            generateParenthesis(s+")",left,right+1,n);
    }
}

Even More
There're many problems that looks totally different at first glance, but are the same in nature.
The key in called Catalan Number. The n th Catalan number is 1/(n+1) * C(2n, n).
So when n=3, we can get Catalan number = 5, which is the total number of well-formed parenthesis combinations when n=3.

No comments:

Post a Comment