Valid Parentheses

Given a string s containing only '(', ')', '{', '}', '[' and ']', return true if it is valid: every opening bracket is closed by the same type of bracket, in the correct order, and every closing bracket has an opening one. This is LeetCode 20.

Example 1

Input: s = "()" Output: true

Example 2

Input: s = "()[]{}" Output: true

Example 3

Input: s = "(]" Output: false Explanation: '(' is closed by the wrong type.

Example 4

Input: s = "([)]" Output: false Explanation: the counts match, but '[' is closed after '(' even though it was opened later.

How to Think About It

Step 1: Counting is not enough

Example 4 has one of each bracket, yet it is invalid. The rule is about order: the bracket opened last must be closed first. Last-opened, first-closed is a stack.

Step 2: Push what you expect to see

For an opening bracket, push the matching closing bracket. Then a closing bracket only has to equal the top of the stack, with no lookup table.

Step 3: Three ways to fail

a closing bracket arrives and the stack is empty (nothing to close);
a closing bracket differs from the top (wrong type or wrong order);
the stack is not empty at the end (something was never closed).

Walkthrough

s = "([)]".

Char	Action	Stack after (expected closers, top last)
(	push ')'	[ ) ]
[	push ']'	[ ), ] ]
)	top is ']', not ')': return false

Java Solution

The default branch handles all three closing brackets with one comparison.

Java

import java.util.ArrayDeque;
import java.util.Deque;

public class ValidParentheses {
    public boolean isValid(String s) {
        Deque<Character> expected = new ArrayDeque<>(); // closing brackets we still need
        for (char c : s.toCharArray()) {
            switch (c) {
                case '(' -> expected.push(')');
                case '[' -> expected.push(']');
                case '{' -> expected.push('}');
                default -> {
                    if (expected.isEmpty() || expected.pop() != c) {
                        return false;
                    }
                }
            }
        }
        return expected.isEmpty(); // every opening bracket was closed
    }
}

The original implementation, ValidParentheses.java, is on GitHub.

Complexity

Time: O(n).
Space: O(n) for the stack.

With only one bracket type a counter is enough, as in Minimum Add to Make Parentheses Valid.