Valid Parentheses LeetCode Solution

Difficulty Level Easy
Frequently asked in Adobe Amazon Apple Blizzard Bloomberg ByteDance Expedia Facebook Goldman Sachs Google IBM lyft Microsoft Oracle Spotify Zillow
BufferedOutputStream String

In Valid Parentheses LeetCode problem we have given a string containing just the characters ‘(‘, ‘)’, ‘{‘, ‘}’, ‘[‘ and ‘]’, determine if the input string is valid. Here we will provide a Valid Parentheses LeetCode Solution to you.

An input string is valid if:

  1. Open brackets must be closed by the same type of brackets.
    • ( )
    • [ ]
    • { }
  2. Open brackets must be closed in the correct order.
    • ()][ not valid
    • (){[]} valid
    • [(){}] valid

Example

Input: str = “[]{()()}”

Output: The given string contains valid parentheses.

Algorithm for Valid Parentheses

n: length of string

str: input string

  1. Declare and initialize a stack S.
  2. Run a loop on i from 0 to n.
    1. If str[i] is an opening bracket, then push str[i] in the stack.
    2. If str[i] is a closing bracket, then there are two possibilities:
      • If the top bracket present in the stack is the opening bracket of the same type, then pop top element of the stack.
      • Else, return false.
  3. Return S.empty().

Working Process Step By Step

str = [{}()]

n = 6

Step 1: we get opening bracket [, hence push [ in stack.

Step 2: we get opening bracket {,hence push { in stack.

Valid Parentheses LeetCode SolutionPin

Step 3: we get a closing bracket } and the top of the stack is {, hence do pop operation on the stack.

Valid ParenthesesPin

 

Step 4: we get opening bracket (, hence push ( in the stack.

See also
Number of Equivalent Domino Pairs Leetcode Solution

Pin

Step 5: we get a closing bracket ) and the top of the stack is (, hence do pop operation on the stack.

 

Valid ParenthesesPin
Valid Parentheses

Step 6: we get a closing bracket ] and the top of the stack is [, hence do pop operation on the stack.

Valid Parentheses LeetCode SolutionPin

Implementation for Valid Parentheses LeetCode Solution

C++ program for Valid Parentheses

#include<bits/stdc++.h>
using namespace std;
bool isValid(string s) {
    stack<char> bracket;
    for (char& c : s) {
        switch (c) {
            case '(': bracket.push(c); break;
            case '{': bracket.push(c); break;
            case '[': bracket.push(c); break;
            case ')': if (bracket.empty() || bracket.top()!='(') return false; else bracket.pop(); break;
            case '}': if (bracket.empty() || bracket.top()!='{') return false; else bracket.pop(); break;
            case ']': if (bracket.empty() || bracket.top()!='[') return false; else bracket.pop(); break;
            default: ; 
        }
    }
    return bracket.empty() ;
}
int main(){
    string s = "[[]{}]()";
    bool check = isValid(s);
    if(check){
        cout<<"The given string contains valid parentheses.";
    }
    else{
        cout<<"The given string contains invalid parentheses.";
    }
}
The given string contains valid parentheses.

JAVA program for Valid Parentheses

import java.util.*; 
public class Main
{
    public static boolean isValid(String s) {
        Stack<Character> bracket = new Stack<>();
        for (char c : s.toCharArray()) {
             switch (c) {
                case '(': bracket.push(c); break;
                case '{': bracket.push(c); break;
                case '[': bracket.push(c); break;
                case ')': if (bracket.empty() || bracket.peek()!='(') return false; else bracket.pop(); break;
                case '}': if (bracket.empty() || bracket.peek()!='{') return false; else bracket.pop(); break;
                case ']': if (bracket.empty() || bracket.peek()!='[') return false; else bracket.pop(); break;
                default: ; 
            }
        }
        return bracket.isEmpty();
    }
  public static void main(String[] args) {
      String s = "{}[)(]";
      boolean check = isValid(s);
          if(check){
                System.out.println("The given string contains valid parentheses.");
            }
            else{
                System.out.println("The given string contains invalid parentheses.");
            }
  }
}
The given string contains invalid parentheses.

Complexity

Time complexity

O(n)

See also
Best Time to Buy and Sell Stock with Transaction Fee Leetcode Solution

where n is the length of the given string as we are traversing the given string for once.

The pop(), top() and push() operation in stack takes constant time.

Space complexity

O(n)

As we can use an extra space of stack and in the worst case, the size of the stack can be n/2

References

1