Stack

Valid Closing Parenthesis - Easy

Can use stacks to check for the closingparenthesis problem.

A much better solution

Uses a dict lookup for pairs, and a Stack. last opened is first closed, just check that match or if stack is empty.

• match? -> pop it
• otherwise false

One loop through (O(n)) and Stacks make this fast albeit a teeny bit memory hungry.

1. Iterate through, if current char is an opening parenthesis/bracket, then add it to the stack (put).
2. Else if the current is a closing parenthesis, check if its a pair with the opener at the top of the stack (peak)
   1. If not pair or stack size is zero -> return False,
   2. else pop the opener from the stack because they’re a pair.
3. If stack size is zero -> return True // cuz means all openers have been paired), else false.

class Solution {
 
    public boolean pair(Character chr, MyStack stack) {
        switch (stack.peak()) {
            case '(':
                if (chr == ')') {
                    return true;
                }
                break;
            case '{':
                if (chr == '}') {
                    return true;
                }
                break;
            case '[':
                if (chr == ']') {
                    return true;
                }
            default:
                return false;
        }
        return false;
    }
 
    public boolean isValid(String input) {
        MyStack stack = new MyStack();
        for (int i = 0; i < input.length(); i++) {
            if (input.charAt(i) == '(' || input.charAt(i) == '{' || input.charAt(i) == '[') {
                stack.push(input.charAt(i));
            } else if (input.charAt(i) == ')' || input.charAt(i) == '}' || input.charAt(i) == ']') {
                if (stack.size() == 0 || !(pair(input.charAt(i), stack))) {
                    return false;
                } else {
                    stack.pop();
                }
            }
        }
        if (stack.size() == 0) {
            return true;
        } else {
            return false;
        }
    }
}