Stack - Valid Parentheses

Given a string s 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.
Every close bracket has a corresponding open bracket of the same type.

Input: s = "()"
Output: true

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

Input: s = "(]"
Output: true

Constraints:

0 <= s.length <= 10⁴
s consists of parentheses only '()[]{}'.

Solution 1 - Using stack to store opening parentheses, and check its validity when a closing parentheses occurrs

In this approach, we are going to use a Stack datastructure to store opening brackets, and when a closing bracket occurred, we will check the corresponding opening bracket and check they are the correct pair, if they are not then return false, otherwise continue checking and at the end check if the stack has any unbalanced entries, return true if it is empty, false otherwise.

Implementation steps:

First, we will create two variables chars a Stack that we will use to store opening brackets, and closeToOpenMap a Map with closing and corresponding opening bracket pair.
Next, loop through input string s characters and check if the characters one of the closing bracket, if it is then check if the stack is not empty and the top element is the corresponding opening bracket, if it is then pop the top element, otherwise return false.
If the current character is an opening bracket, then simply add it to the stack chars.
Finally, check if the stack is empty, if it is empty return true, otherwise return false. (If every opening bracket has a valid corresponding closing bracket, then stack will be empty at the end)

package io.cscode.algorithms.stack; import java.util.Map; import java.util.Stack; public class ValidParentheses { static boolean isValid(String s) { Stack<Character> chars = new Stack<>(); Map<Character, Character> closeToOpenMap = Map.of(')', '(', ']','[','}','{'); for(char c : s.toCharArray()) { if(closeToOpenMap.containsKey(c)) { if(!chars.isEmpty() && closeToOpenMap.get(c).equals(chars.peek())) { chars.pop(); } else { return false; } } else { chars.push(c); } } return chars.isEmpty(); } public static void main(String[] args) { System.out.println(isValid("()")); System.out.println(isValid(")(")); System.out.println(isValid("(]")); System.out.println(isValid(")")); } }

Complexity Analysis:

Time complexity: Above code runs in O(n) time where n is the length of input string s.
Space complexity: O(n), since we are storing opening brackets into a Stack.

Above implementations source code can be found at GitHub link for Java code

Constraints:

Contents

Implementation steps:

Complexity Analysis: