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.

2 comments:

  1. They let you know that a $200 bet can be required to generate a $100 profit. Essentially, it means you'll earn 50% of your bet amount in profit. For example, a $200 bet would net you $100 in winnings, whereas a $40 bet at -200 코인카지노 would earn you a $20 profit. Sportsbooks provide a main point spread, puck line and run line. They either make things easier for you in exchange for a smaller potential payout or make things tougher in exchange for a larger potential payout. If the percentages begin with a plus (+), the numbers highlight the profit you'll earn by putting a $100 bet.

    ReplyDelete
  2. Each 8-to-1 corner that covers 4 numbers) may have $4,000 wagered on it. Each 11-to-1 street that covers three numbers may have $3,000 wagered on it. Each $1,000 incremental bet would be represented by a marker that is used to specifically determine the player and the amount bet. Although most frequently named "call bets" technically these bets are more accurately referred to as "announced bets". The authorized distinction between a "call bet" and an "announced bet" is that a "call bet" is 카지노사이트 a bet called by the player with out him placing any cash on the table to cowl the cost of|the value of} the bet. In many jurisdictions this is thought-about gambling on credit and is illegal the law|is unlawful}.

    ReplyDelete