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:

  1. Every opening parenthesis should be closed by the same kind of parenthesis. Therefore, {) and [(]) strings are invalid.

  2. Every opening parenthesis must be closed in the correct order. Therefore, )( and ()(() are invalid.

Constraints:

  • 1≤1 \leq exp.length ≤103\leq 10^3

  • 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:

  1. We start by creating an empty stack, stack. This stack will keep track of opening parentheses as we encounter them in the string.

  2. We then iterate through each character in exp. For this step, we consider two main actions:

    1. Whenever we encounter an opening parenthesis ( or { or [, we push it onto the stack.

    2. Upon encountering a closing parenthesis ) or } or ], we check the stack:

      1. 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.

      2. 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.

  3. After completing the iteration over exp, we perform one last check:

    1. If the stack is empty, every opening parenthesis has been successfully matched with a closing parenthesis. Thus, the parentheses exp are balanced, and we return TRUE.

    2. 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 70+ hands-on prep courses.