Valid Parentheses LeetCode Solution

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.

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

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

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

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

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)

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