20. Valid Parentheses

Brackets have LIFO structure: the latest opener must be the next to close. A stack models that exactly. Push each opener; on a closer, verify the top matches.

Approach

1. Keep a stack st.
2. For each char c:
   • If c is an opener, push it.
   • Else if stack is empty or top doesn't match c, return False.
   • Else pop.
3. Valid iff stack is empty at the end.

import java.util.*;

class Solution {
    public boolean isValid(String s) {
        Map<Character, Character> pair = new HashMap<>();
        pair.put(')', '(');
        pair.put(']', '[');
        pair.put('}', '{');
        Deque<Character> st = new ArrayDeque<>();
        for (char c : s.toCharArray()) {
            if (c == '(' || c == '[' || c == '{') {
                st.push(c);
            } else {
                if (st.isEmpty() || st.pop() != pair.get(c)) return false;
            }
        }
        return st.isEmpty();
    }
}