Data Structures & Algorithms in Java – Strings – Valid Parantheses


Given a string containing parantheses ( (,).{,},[,]) check if the parantheses match or not.

For example,

The string “()[]{}” is a valid string because the opening parentheses are matched by closing ones.

The string “{[()]}” is also a valid expression since all the opening parentheses have corresponding closing parentheses

The string “(]” is invalid .

The string “({)}” is also invalid though there are matching parantheses because they are not in the correct positions.

For every opening parentheses , whatever parentheses comes in between the opening and closing parentheses should be closed.

Try out the solution here:




  • Use a stack data structure


STEP 1: Initialize a stack to store the parenthesis

STEP 2: For every character in the string , check the top character in the stack.

STEP 2a: If the current character is the closing parenthesis of the top character then pop it out, else add the character to the stack.

STEP 3: If the stack is empty at the end , then the given string is valid , return true . Else return false.


class Solution {
    public boolean isValid(String s) {
        Stack<Character> stack = new Stack<Character>();
        for(char c: s.toCharArray()){
             boolean popped = false;
                char top = stack.peek();
                if(top == '('  && c == ')' || top == '{' && c == '}' || top == '[' && c == ']'){
                    popped = true;
            return true;
        return false;

Time complexity is O(n) where n is the length of the string and space complexity is also O(n) to store the n characters in the stack.

That’s it!

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s