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

Anti Diagonals - The Coding Shala

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

LeetCode - Bulb Switcher Solution - The Coding Shala

New Year Chaos Solution - The Coding Shala

Sorting the Sentence LeetCode Solution - The Coding Shala