LeetCode — Valid Parentheses

Problem Link: https://leetcode.com/problems/valid-parentheses/

Photo by Bekir Dönmez on Unsplash

Problem Description: Given a string s containing just the characters '(', ')', '{', '}', '[' and ']', determine if the input string is valid.
An input string is valid if:
i) Open brackets must be closed by the same type of brackets.
ii) Open brackets must be closed in the correct order.

Example 1:
Input: s = "([)]"
Output: false
Example 2:
Input: s = "{[]}"
Output: true

Approach Used: Stack

Explanation: In this problem, we need to check if the parenthesis is balanced or not. The explanation is pretty straight forward. If there is an opening bracket is found, then there should either be a closing bracket of the same type or another opening bracket for it to be valid. If another opening bracket was found, then the opening bracket found later should be closed first.
This is a very standard stack question. Since opening bracket that came later should be closed first or Last in First Out(LIFO), the best way to solve it would be using a stack data structure. We can maintain a stack of opening brackets i.e. that if we encounter an opening bracket we simply push it into the stack to ensure we know the order of entry and whenever we find a closing bracket we check if it matches the last inserted or the last opening bracket whose closing bracket was not found. If so we remove the opening bracket as this pair is complete. If it mismatches then parenthesis is not balanced and hence we do not need to check further. Another case of invalidity would when there are no opening brackets in the stack and we have a closing bracket which means it is extra. The last case of invalidity would be when we have traversed through all the character of the string and there are still some opening brackets left in the stack which means that closing brackets for them were not found. If none of the invalid cases was encountered then we return true at the end.

Code: (Java)

public boolean checkUsingStack(String s){
        Stack<Character> openBracketsInOrder = new Stack<>();
int index=0;
        while(index<s.length()){
if(s.charAt(index) == '(' || s.charAt(index) == '{' || s.charAt(index) == '[')
                openBracketsInOrder.push(s.charAt(index));
            else{
                if(openBracketsInOrder.empty())
                    return false;
Character lastBracketType = openBracketsInOrder.pop();
                if((s.charAt(index)==')' && lastBracketType!='(') ||
                (s.charAt(index)=='}' && lastBracketType!='{') ||
                (s.charAt(index)==']' && lastBracketType!='['))
                    return false;
            }
index++;
        }
return openBracketsInOrder.empty();
    }
    
    public boolean isValid(String s) {
        return checkUsingStack(s);
    }

Complexity:
Space Complexity: O(N). If all the characters in the string are opening brackets, then that’ll be the size of the stack
Time Complexity: O(N). In cases where parenthesis is actually balanced, we need to check each character of the string before returning true and hence the given complexity.
Here N is the length of the string.

The Github link contains code with comments for a better explanation.
Github Link:
https://github.com/siddhaant-jain/LeetCode/blob/master/DailyChallenge/src/CodeFiles/ValidParentheses.java