Valid Parantheses

Valid Parentheses

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

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.

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

Solution:

This is a very basic problem that every programmer should know if he knows stack data structure. This problem can also be asked in different ways like if we have to design a compiler to check for an balanced parenthesis.

Every opening parenthesis should have it’s closing parenthesis and the order must be taken into consideration also. Stack data structure is only efficient way to solve this problem.

Algorithm:

1. Initialize a character Stack.
2. Take one bracket at a time as a character.
3. If the bracket is an opening bracket, we will push it to the stack.
4. If the bracket is a closing bracket then we will look for the opening bracket which has been already being pushed into the stack. If we find an opening bracket at the top of the stack and of the same type, then we will pop out the opening bracket, this is done to show that we have found a pair in a same order and we do not need that pair anymore.
5. If we found different type of bracket on the top of the stack or the stack is already empty then we simply return false as the parenthesis given is not valid.
6. In the end, if our stack is still not empty then we can say that the given input is not valid parenthesis.

Implementation:

Solution:

class Solution1 {
    public boolean isValid(String s) {
        Stack<Character> stack = new Stack<>();
        for (int i = 0; i < s.length(); i++) {
            if (s.charAt(i) == '(' || s.charAt(i) == '{' || s.charAt(i) == '[') {
                stack.push(s.charAt(i));
            } else {
                if (stack.isEmpty()) {
                    return false;
                } else {
                    if (stack.peek() == '(' && s.charAt(i) != ')') {
                        return false;
                    } else if (stack.peek() == '{' && s.charAt(i) != '}') {
                        return false;
                    } else if (stack.peek() == '[' && s.charAt(i) != ']') {
                        return false;
                    }
                    stack.pop();
                }
            }
        }
        return stack.isEmpty();
    }
}

Complexity Analysis:

• Time Complexity: O(n) because we simply traverse the given string one character at a time and push and pop operations on a stack take O(1) time.
• Space Complexity: O(n).