Mayank Jaiswal
BAN USERYes, the values of nodes can be from 1 to n and every node has a unique value.
- Mayank Jaiswal February 03, 2012Let us start by understanding the problem.
Here are a few examples:
( ) -- correct
( ( ) ) -- correct
( ( ) ) ( ) -- correct
( ( ( ) ) ( ) ) -- correct
( ) ) -- incorrect (closed paren with no open paren)
) ( -- incorrect
( ( ) ) ) ( -- incorrect
As you can see, the number of open and closed parens being equal does not guarantee that the parens are matching. Their order is important too.
We take care of this order using a stack.
An algorithm that checks whether the matching in a given text is correct is as follows:
0. Create an empty stack S.
1. While( there are characters left ){
2. Read a character ch.
3. If is ch an opening paren (of any kind), push it onto S
4. Else
5. If ch is a closing paren (of any kind), look at the top of S.
6. If S is empty as this point, report failure.
7. If the top of S is the opening paren that corresponds to c,
then pop S and continue to 1, this paren matches OK.
8. Else report failure.
9. If at the end of input the stack S is not empty, return failure.
Else return success.
I am sorry Rahul but above solution is incorrect because it doesn't take care of the fact that an opening parenthesis should come before its corresponding closing parenthesis.
In parenthesis matching, parenthesis must open before closing just like any valid mathematical expression.
Correct examples:
1. ((()))
2. () () ()
3. (()) ()
Incorrect :
1. ((( ))))
Incorrect because no. of opening parenthesis is not equal to no. of closing parenthesis.
2. )(
Incorrect because closing parenthesis comes before corresponding opening parenthesis.
The above solution is wrong! It returns true even on input "}}{{".
For correct solution, a stack must be used.
Repjimbtam, Backend Developer at ASAPInfosystemsPvtLtd
I was extremely into photography for a number of years.My father was also interested in photography, so I was ...
Repjunehudson, Associate at Advisory Board Company
I am passionate about fashion and love to explore black magic to take revenge.Being a fashion designer involves more ...
This in an O(n log n) solution.
- Mayank Jaiswal February 05, 2012Explanation :
We divide the array in four sections:[X,Y|A,B]
It is easy to see that with swaps we can modify it to the form [X,A|Y,B].
Now do recursion to solve [X|A] and [Y|B] separately,essentially using divide and conquer.
-------------------------------------
For example:
Original Array: [X,Y|A,B] = { 1,2,3,4,5,6,7,8,a,b,c,d,e,f,g,h }
where X = { 1,2,3,4 }, Y = { 5,6,7,8 }, A = { a,b,c,d }, B = {e,f,g,h}
Now, swap sections Y and A
New array : [X,A|Y,B] = { 1,2,3,4,a,b,c,d,5,6,7,8,e,f,g,h }
We now have divided original problem in to two similar sub problems by doing n/2 swaps.
We can use recursion to solve the sub problems now.
-------------------------------------
Complexity Analysis :
T(n) = 2T(n/2) + O(n)
=> T(n) = O(n log n)