Problem #20: Valid Parentheses

Intuition & Strategy Breakdown

Use a stack to track open brackets. When encountering a closing bracket, check if the stack top matches the corresponding opening bracket type; return true if stack is empty at the end.

Python Solution

class Solution:
    def isValid(self, s: str) -> bool:
        stack = []
        mapping = {")": "(", "}": "{", "]": "["}

        for char in s:
            if char in mapping:
                top_element = stack.pop() if stack else '#'
                if mapping[char] != top_element:
                    return False
            else:
                stack.append(char)
        
        return not stack

Java Solution

class Solution {
    public boolean isValid(String s) {
        Stack stack = new Stack();
        Map mapping = new HashMap();
        mapping.put(')', '(');
        mapping.put('}', '{');
        mapping.put(']', '[');

        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            if (mapping.containsKey(c)) {
                char topElement = stack.empty() ? '#' : stack.pop();
                if (topElement != mapping.get(c)) {
                    return false;
                }
            } else {
                stack.push(c);
            }
        }
        return stack.isEmpty();
    }
}