Solution: Valid Parentheses
Let’s solve the Valid Parentheses problem.
We'll cover the following
Statement
Given a string, exp
, which may consist of opening and closing parentheses. Your task is to check whether or not the string contains valid parenthesization.
The conditions to validate are as follows:
Every opening parenthesis should be closed by the same kind of parenthesis. Therefore,
{)
and[(])
strings are invalid.Every opening parenthesis must be closed in the correct order. Therefore,
)(
and()(()
are invalid.
Constraints:
exp.length
The string will only contain the following characters:
(
,)
,[
,]
,{
and}
.
Solution
The essence of this problem lies in finding valid pairs of opening and closing parentheses in exp
. For this purpose, we create a stack to keep track of the opening parentheses in the string. While iterating over the string, if we encounter any opening parenthesis, we push it onto the stack. When we encounter a closing parentheses, we compare it to the last opening parentheses pushed onto the stack. If they match, we continue. Otherwise, the string exp
is unbalanced and we return FALSE. If every opening parentheses has a corresponding closing parentheses, the stack will be empty when we complete iterating the string and return TRUE.
The solution can be broken down into the following key steps:
We start by creating an empty stack,
stack
. This stack will keep track of opening parentheses as we encounter them in the string.We then iterate through each character in
exp
. For this step, we consider two main actions:Whenever we encounter an opening parenthesis
(
or{
or[
, we push it onto the stack.Upon encountering a closing parenthesis
)
or}
or]
, we check the stack:If the
stack
is empty, this means that there’s no opening parenthesis available to match the closing one, indicating that the parentheses are unbalanced. We return FALSE in this scenario.If the
stack
is not empty, we pop an element of the stack. This popped element should be the opening parenthesis corresponding to the closing one we’re currently processing. If they don’t match, we return FALSE.
After completing the iteration over
exp
, we perform one last check:If the
stack
is empty, every opening parenthesis has been successfully matched with a closing parenthesis. Thus, the parenthesesexp
are balanced, and we return TRUE.Otherwise, we return FALSE because
stack
contains opening parentheses without corresponding closing parentheses.
The following illustration shows these steps in detail:
Level up your interview prep. Join Educative to access 80+ hands-on prep courses.