Check for Balanced Parenthesis

In this article, we will solve the problem of checking if a string has balanced parentheses.

Problem Statement: Given a string containing characters (, ), {, }, [ and ], we need to determine if the string has balanced parentheses. A string is considered balanced if:

• Every opening bracket has a corresponding closing bracket.

• The brackets are closed in the correct order.

Examples:

Input: s = "({[]})" Output: true

Input: s = "([)]" Output: false

Solution:

To solve this problem, we will use a stack data structure.

Steps to Solve:

1.    Initialize a Stack:

o   Create an empty stack to keep track of opening brackets.

2.    Iterate Through the String:

o   For each character in the string:

§  If the character is an opening bracket ((, {, [), push it onto the stack.

§  If the character is a closing bracket (), }, ]):

§  Check if the stack is empty. If it is, return false because there is no corresponding opening bracket.

§  Otherwise, pop the top element from the stack and check if it matches the closing bracket. If it doesn't match, return false.

3.    Check the Stack:

o   After processing all characters, if the stack is empty, return true because all brackets are balanced.

If the stack is not empty, return false because there are unmatched opening brackets.

Time Complexity: O(N)

Space Complexity: O(N)