Valid parentheses - Leetcode

Introduction

Valid parentheses is an standard problem based on stacks, it's a simple program but asked in different interviews of big tech giants as well like Facebook, Amazon, Microsoft, Apple, Google, and other tech companies.

Problem Statement

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.

Example 1 -

Input: s = "()"
Output: true

Example 2 -

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

Example 3 -

Input: s = "(]"
Output: false

Explanation -

A valid parentheses is basically a pair of parentheses present in the string together. Here we'll use stack to check for a valid parentheses.

We have to check for three types of Brackets (), [], {}, to reduce the code duplication let's make functions 🗿(it's rather fun with functions) and it make the code more readable.

To check left brackets we got the leftBracket function which will check if the current character is a opening bracket, if yes then Push it into the stack.

Similarly, To check right brackets we got the rightBracket function which will check if the current character is a closing bracket, if yes then check whether the stack is Empty if Yes then that means out first character is a closing bracket without an opening bracket so return false.

Otherwise pop out the top element from the stack and compare the top element and the current character whether they shares same type of opening and closing bracket.

To compare we got another, sigh, yeah you guessed it right Function. matchBracket function returns true if top of stack and current character is not same type of opening and closing brackets we'll return false else we'll continue the same process for rest of the characters of the string.

Pseudo code

loop
  if(currentCharacter == opening brackets)
    push into stack
  if(currentCharacter == closing brackets)
    if(stack is empty)
      return false
    else
      pop out top element from stack
      if(topElement and currentElement is not same kind of opening and closing brackets)
        return false
loop ends
return true if stack is empty

Try Yourself Before Seeing the Code

Code -

public boolean isValid(String s) {
    Stack<Character> stack = new Stack<>();
    for(char ch : s.toCharArray()){
        if(leftBracket(ch))
            stack.push(ch);
        if(rightBracket(ch)) {
            if(stack.isEmpty())
                return false;
        char top = stack.pop();
        if(matchBracket(ch, top))
            return false;
        }
    }
    return stack.isEmpty();
}

boolean leftBracket(char ch){
    return ch == '(' || ch == '[' || ch == '{';
}

boolean rightBracket(char ch){
    return ch == ')' || ch == ']' || ch == '}';
}

boolean matchBracket(char ch, char top){
    return (ch == ')' && top != '(') ||
           (ch == ']' && top != '[') ||
           (ch == '}' && top != '{');
}

Time Complexity - o(n), Linear time as we're only iterating once through the string.

Space Complexity - O(n), in worst case with the string only consist of opening backets we'll get O(n) time complexity