Sweaty Imposter

Valid Parentheses

EasyStackBlind 75JuniorOpen on LeetCodeUpdated

You're given a string s made only of the characters '(', ')', '[', ']', '{' and '}'. Return true if its brackets are valid and false otherwise. The brackets are valid when every opening bracket is closed by a bracket of the same type, pairs close in the correct order (they may nest but never cross), and every closing bracket has a matching opener before it. Having equal counts of each type is not enough.

Examples

s = "{[]}()" returns true

The square pair sits entirely inside the curly pair, and the round pair follows on its own. Every opener is closed by the matching type in the right order.

s = "([)]" returns false

The ) arrives while [ is still open inside the (, so the pairs cross. Each type appears once opened and once closed, but the order is wrong.

s = "(()" returns false

The inner pair matches, but the first ( is never closed.

Constraints

  • 1 <= s.length <= 10^4
  • s consists of parentheses only: '()[]{}'.

Hints

Hint 1

When a closing bracket shows up it has to match one specific opener. Is that the first bracket that was opened, or the most recent one still waiting to be closed?

Hint 2
A pointer toward the approach
Hint 3
The full approach, step by step

Drill This: Your Approach First

Approach

The next closer may only match the most recently opened bracket that is still open, which is last-in, first-out order, so a stack fits exactly. For each opener push the closer you expect; for each closer, the stack must be non-empty and its top must equal that closer, then pop. After the scan the string is valid only if the stack is empty, meaning nothing is left open. O(n) time, O(n) space when the string is all openers.

Time

O(n)

Space

O(n)

Pitfall

Returning true when the loop ends without checking that the stack is empty, so "(()" passes. The opposite bug is popping when nothing is open: a string that starts with a closer, like "]", must return false instead of crashing.

Solutions

class Solution {
    public boolean isValid(String s) {
        Deque<Character> stack = new ArrayDeque<>();
        for (char c : s.toCharArray()) {
            if (c == '(') stack.push(')');
            else if (c == '[') stack.push(']');
            else if (c == '{') stack.push('}');
            else if (stack.isEmpty() || stack.pop() != c) return false;
        }
        return stack.isEmpty();
    }
}
Drill This