Array ( [0] => [1] => questions [2] => Basic [3] => Balanced-Parenthesis ) Strings | Balanced Parenthesis | THE INQUISITIVE






Balanced Parenthesis

LEVEL:Beginner

Description

Given a String with {,},(,),[,] characters. You have to find the given string is balanced or not.

Input Format

First line contains a string. Next line also contains a string.

Output Format

Print Yes if the given string is balanced else No.


Example 1:

Input
({[]()[]})
Output
Yes
Example 2:

Input
{}[]()
Output
Yes
Example 3:

Input
{)(}
Output
No

oops

Login to see Discussion




Approach

Approach 1: Using Stack

Step-i)Create a stack of characters
Step-ii) Traverse through the string and push to stack if there are any open brackets
Step-iii) Pop from stack if top element and closing bracket are same
Step-iv) If they are not same return "Not Balanced"
Step-v) Repeat ii, iii, iv till all the characters of the string are traversed
Step-vi) check if stack is empty or not
Step-vii) If stack is empty return "Balanced" else return "Not Balanced"

Time Complexity: O(n)
Space Complexity: O(n) as stack may grow to the size of string when all are open parenthesis

Approach 2: Using variable to keep track of parenthesis

Step-i) Initialize three variables to 0 which represent three types of parenthesis
Step-ii) Traverse the string if found any open parenthesis then increment respective variable
Step-iii)if found any closed parenthesis decrement respective variable
Step-iv) If any variable is negative return "Not Balanced"
Step-v) Repeat steps ii, iii and iv till you traverse the entire list
Step-vi) check if all the variables which represent parenthesis are zero or not
Step-vii) If they are zero return "Balanced" else "Not Balanced"

Time Complexity: O(n)
Space Complexity: O(1) we only need three variables to keep track of parenthesis


Note :

Let us know if you can come up with a better approach, mail us at support@theinquisitive.in Your approach will be reviewed and posted with credits to you.

oops

Login to see Solution






     Recommended Questions      

Topic: Strings

Beginner

1. Timing Format2. Date Format3. Palindrome 4. Anagrams5. Balanced Parenthesis6. Equal Strings7. Smallest Window8. Reverse of String9. Distinct Palindromes10. Remove adjacent duplicates11. Run length encoding12. Non repeating Character13. Array of strings14. Find Excel Column15. Transform one string to another16. Move Robot in circular17. Zig Zag concatenation. 18. Min No of elements19. Combination of strings used to dial a number20. Ancient String