Valid Parenthesis

Question (LC.20)

Given a string that includes three types of brackets, (), [], and {}, determine if all brackets match in the correct order.

Example

Input: ()[]{}
Output: true
Input: ([)]
Output: false

Analysis

Create a Map<BracketType, Frequency> then checking the frequency == 0 won't work because we also care about the order that they are in. In order to preserve this order, we put the open brackets into a stack then pop it to match with the closed brackets.

Approach

iterate through the input string
    push open brackets onto a stack
    pop from stack when closed brackets are detected
        if the stack is empty, return false (more closed than open)
        if the brackets don't match (wrong type), also return false
return if the the stack is empty (all open and closed match)

Code

Main Function

public boolean isValid(String s) {
    if (s == null) {
        return false;
    }
    Stack<Character> stack = new Stack<>();
    Set<Character> openBrackets = new HashSet<>();
    openBrackets.add('(');
    openBrackets.add('[');
    openBrackets.add('{');

    for (int i = 0; i < s.length(); i++) {
        char cur = s.charAt(i);
        if (openBrackets.contains(cur)) {
            stack.push(cur);
        } else {
            if (!stack.isEmpty() && checkClosed(stack.peek(), cur)) {
                stack.pop();
            } else {
                return false;
            }
        }
    }
    return stack.isEmpty();
}

Check if brackets match

private boolean checkClosed(char open, char closed) {
    if (open == '(') {
        return closed == ')';
    }
    if (open == '[') {
        return closed == ']';
    }
    if (open == '{') {
        return closed == '}';
    }
    return false; // invalid input
}

Reflection

"Easy" questions are as easy you think to make a one pass. The logic has to make perfect sense. Edges cases have to be all covered. No typos and grammar issues. Do not get lazy on testing manually. The ONLY way to make sure your programing works is to run through a couple examples.