Valid Parentheses Problem - The Coding Shala

Home >> Interview Questions >> Valid Parentheses

Valid Parentheses Problem

Given a string 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.
  • Note that an empty string is also considered valid.
Example 1:
Input: "()"
Output: true

Example 2:
Input: "()[]{}"
Output: true

Example 3:
Input: "(]"
Output: false

Example 4:
Input: "([)]"
Output: false

Example 5:
Input: "{[]}"
Output: true

Valid Parentheses Java Program

Method 1:
We can do this using a stack. Push into the stack if opening brackets come else check with the top element of the stack with a closing bracket.

Java Code: 

class Solution {
    public boolean isValid(String s) {
        int len = s.length();
        if(len == 0) return true;
        Stack<Character> st = new Stack<Character>();
        for(int i=0;i<len;i++){
            char ch = s.charAt(i);
            if(ch == '(' || ch == '{' || ch =='[') st.push(ch);
            else{
                if(st.empty()) return false;
                char pp = st.pop();
                if(pp=='(' && ch ==')') continue;
                if(pp =='{' && ch=='}') continue;
                if(pp =='[' && ch==']') continue;
                return false;
            }
        }
        if(st.empty()) return true;
        return false;
    }
}



Other Posts You May Like
Prev<< Longest Common Prefix                                                                  NEXT >>Reverse Words in a String
Please leave a comment below if you like this post or found some error, it will help me to improve my content.

Comments

Popular Posts from this Blog

Shell Script to find sum, product and average of given numbers - The Coding Shala

Java Program to Convert Binary to Decimal - The Coding Shala

N-th Tribonacci Number Solution - The Coding Shala

Shell Script to Create a Simple Calculator - The Coding Shala

InterviewBit - Colorful Number Solution - The Coding Shala