Solve valid parentheses problem

In this post we are gonna discuss how to solve valid parentheses problem using stack

Problem Statement:

Given a string containing just the characters '(', ')', '{', '}', '[' and ']', determine if the input string is valid.

An input string is valid if:

Open brackets must be closed by the same type of brackets.

Open brackets must be closed in the correct order.

Note that an empty string is also considered valid.

Example 1:

Input: "([)]"
Output: false

Example 2:

Input: "{[]}"
Output: true

Step by step solution to the problem :

This is a straight forward problem which can be easily solved using stack.

First we define an empty stack and map containing correct opening braces for corresponding closing braces.

Now we check if the character at current index is any one of ‘(’,’[’ or ‘{’, then push current index character to stack or if the character at current index is any one of ‘)’,’]’ or ‘}’ we pop from stack and check popped character if is it matching with starting braces pair from map. If matching then go ahead for next character else not valid.

At last we check if the stack is empty then we conclude the parenthesis is valid else not.

The complete code for this problem can be found in https://github.com/GyanTech877/algorithms/blob/master/stack/ValidParentheses.java

Happy Learning 😎