Valid Parentheses

1package pkg5leetcode;2 3/*4 * LeetCode 20: Valid Parentheses  (Easy)5 * --------------------------------------6 * Given a string of brackets, determine if it is validly closed/nested.7 *8 * APPROACH: push opens onto a stack; on a close, the top must be its match.9 * COMPLEXITY: Time O(n), Space O(n).10 */11import java.util.*;12 13public class leetcode2ValidParentheses {14 15    static boolean isValid(String s) {16        Deque<Character> stack = new ArrayDeque<>();17        Map<Character, Character> pairs = Map.of(')', '(', ']', '[', '}', '{');18        for (char c : s.toCharArray()) {19            if (pairs.containsValue(c)) {20                stack.push(c);21            } else if (pairs.containsKey(c)) {22                if (stack.isEmpty() || stack.pop() != pairs.get(c)) return false;23            }24        }25        return stack.isEmpty();26    }27 28    public static void main(String[] args) {29        check(isValid("()"), "()");30        check(isValid("()[]{}"), "()[]{}");31        check(!isValid("(]"), "(]");32        check(!isValid("([)]"), "([)]");33        check(isValid("{[]}"), "{[]}");34        check(!isValid("("), "(");35        System.out.println("leetcode2ValidParentheses: all tests passed");36    }37 38    static void check(boolean cond, String name) {39        if (!cond) throw new AssertionError("FAILED: " + name);40        System.out.println("  PASS " + name);41    }42}