Solution: Valid Parentheses

Statement#

Given a string that 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 \leq$ string.length $\leq 10^4$
• The string will only contain the following characters: (, ), [, ], { and }.

Solution#

To determine whether or not a string of brackets is valid, we can use a stack data structure to keep track of the opening brackets in the string. We also use a hashmap to map closing brackets to their corresponding opening brackets. The process involves iterating through each character in the input string and checking if it is an opening or closing bracket.

If the character we encounter is an opening bracket, we will push it onto the stack. If it is a closing bracket, we retrieve the corresponding opening bracket from the hashmap using the closing bracket as the key. If the retrieved opening bracket does not match the top element of the stack, we will return FALSE.

After iterating through the entire input string, we check if the stack is empty to ensure all opening brackets have matched their corresponding closing brackets. If it is, we return TRUE, indicating that the string of brackets is valid. Otherwise, it means that some opening brackets have not been closed properly, and we return FALSE to indicate that the string is invalid.

In summary, using a stack and a hashmap data structure, we can easily keep track of the opening and closing brackets in a string to determine whether it is valid. By comparing each closing bracket to the top element of the stack, we can ensure that each opening bracket has a corresponding closing bracket.

Let’s look at the following illustration to get a better understanding of the solution:

Let’s take a look at the code for this solution below:

Time complexity#

The time complexity will be $O(n)$, where $n$ is the number of characters in the input string.

Space complexity#

The space complexity of this solution is $O(n)$, where $n$ is the space required by the stack.