Judging Valid Parentheses

Leetcode problem 20: Valid Parentheses

Question:

Given a string s 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.

Below is one of the solutions:

class Solution {

    // Initialize HashMap
    static final HashMap<Character, Character> hashMap = new HashMap<>();
    static {
        hashMap.put(')', '(');
        hashMap.put('}', '{');
        hashMap.put(']', '[');
    }

    public boolean isValid(String s) {
        // Initialize a stack to be used in the algorithm.
        Stack<Character> stack = new Stack<>();
        for(int i = 0; i < s.length(); i++){
            char c = s.charAt(i);
            // If the current character is a closing bracket
            if(hashMap.containsKey(c)){
                // Get the top element of the stack
                // If the stack is empty, set a dummy value of '#'
                char topElement = stack.empty() ? '#' : stack.pop();
                // If the mapping for this bracket doesn't match the stack's top element, return false;
                if(topElement != hashMap.get(c)){
                    return false;
                }
            }else{
                // If it was an opening bracket, push to the stack.
                stack.push(c);
            }
        }
        return stack.isEmpty();
    }
}

Let's do the test:

First test case:

Input:

"(()){[()]}"

Output:

true

And another test case:

Input:

"](())"

Output:

false

OK! Let's keep practising.