Valid Parentheses

Given a string 's' containing the characters '(' , ')', '{', '}' ,'[' and ']' determine if the input string is valid.

valid condition:

• 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: false

Approach

Java

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Stack;

public class CheckValidParentheses {

public static void main(String args[]) {
    String str="{[}]";
    if(isValid(str))
      System.out.println(str+" Valid Parentheses");
    else
      System.out.println(str+" Not Valid Parentheses");
    }

    public static boolean isValid(String s) {
     
     ArrayList<String> push=new ArrayList<>(Arrays.asList("(","[","{"));
     ArrayList<String> pop=new ArrayList<>(Arrays.asList(")","]","}"));
     Stack<String> stack=new Stack<String>();
        for(int i=0;i<s.length();i++)
        {
            char c=s.charAt(i);
            
            if(push.indexOf(""+c)!=-1)
            {
                stack.push(""+c);
            }
            else if(pop.indexOf(""+c)!=-1 && (stack.size()==0 
               || push.indexOf(stack.peek())!=pop.indexOf(""+c))){
                 return false;
            }else {
                stack.pop();
            }
            
        }
        if(stack.size()!=0) return false;
       return true;
       
    }
}

C++

#include <bits/stdc++.h>
using namespace std;
//function to check valid
//parentheses
bool isValid(string s)
{
    //stack to hold the opening brackets
    stack<char> st;
    int n=s.size();
    for(int i=0;i<n;i++)
      {
          //if open bracket push into the stack
          if(s[i]=='('||s[i]=='{'||s[i]=='[')
             st.push(s[i]);
          else 
           {
              //stack is empty
               if(st.empty())
                 return false;
            //closing bracket not matches with the top 
            //of stack return false
               else if(s[i]==')'&&st.top()!='(')
                  return false;
               else if(s[i]==']'&&st.top()!='[')
                  return false;
              else if(s[i]=='}'&&st.top()!='{')
                 return false;
              st.pop();
           }
      }
    if(!st.empty())
       return false;
    return true;
}
int main()
{
    string str="{[]}";
    if(isValid(str))
       cout<<"Valid Parentheses\n";
    else
      cout<<"Not Valid Parenthese\n";
    return 0;
}
//Time Complexity:O(n)
//Space Complexity:O(n)