Valid Parentheses

Given a String containing only the characters (, ), [, ], {, and }, return true if it's valid:

1. Every opening bracket is closed by a bracket of the same type.
2. Brackets close in the correct order: the most recently opened one is closed first.
3. Every closing bracket has a matching opening bracket.

LeetCode: 20. Valid Parentheses

Examples

"()[]{}"   true
"{[()]}"   true
"([)]"     false   [ is opened last, so it must be closed before )
"(("       false   never closed
"))"       false   closed without being opened

Brute force: delete matched pairs until nothing changes

Any valid string that isn't empty contains at least one innermost pair with nothing between its brackets: (), [], or {}. Removing it leaves a valid string. So remove innermost pairs repeatedly. If the string ends up empty, it was valid. If a round removes nothing and the string isn't empty, it's invalid.

"{[()]}"  ->  "{[]}"  ->  "{}"  ->  ""     valid
"([)]"    ->  no "()", "[]" or "{}" inside, and not empty   invalid

public class Main {
    static boolean isValid(String s) {
        while (true) {
            String shorter = s.replace("()", "").replace("[]", "").replace("{}", "");
            if (shorter.length() == s.length()) {
                return s.isEmpty();
            }
            s = shorter;
        }
    }

    public static void main(String[] args) {
        for (String s : new String[]{"()[]{}", "{[()]}", "([)]", "((", "))"}) {
            System.out.print(isValid(s) + " ");
        }
        System.out.println();
    }
}

true true false false false

Time: O(n²): up to n/2 rounds, each copying the string. Space: O(n).

Optimal: a stack of expected closing brackets

Scan the string once:

• On an opening bracket, push the closing bracket you now expect (an ArrayDeque<Character>, where push and pop work at the top). For (, push ).
• On a closing bracket, pop the stack. The popped bracket must be exactly this character. If the stack was empty, or held a different bracket, the string is invalid.

At the end, the stack must be empty. Otherwise some brackets were never closed.

Walkthrough with "{[()]}":

And with "([)]": after ( and [ the stack is [), ]]. The next character is ), but the popped bracket is ], so the string is invalid.

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

public class Main {
    static boolean isValid(String s) {
        Deque<Character> expected = new ArrayDeque<>();
        for (char c : s.toCharArray()) {
            switch (c) {
                case '(' -> expected.push(')');
                case '[' -> expected.push(']');
                case '{' -> expected.push('}');
                default -> {
                    Character top = expected.poll(); // null when the stack is empty
                    if (top == null || top != c) {
                        return false;
                    }
                }
            }
        }
        return expected.isEmpty();
    }

    public static void main(String[] args) {
        for (String s : new String[]{"()[]{}", "{[()]}", "([)]", "((", "))", ""}) {
            System.out.print(isValid(s) + " ");
        }
        System.out.println();
    }
}

true true false false false true

Time: O(n). Space: O(n) in the worst case, when the string is all opening brackets.

The check top == null || top != c covers two failures: poll() returns null for a closer with nothing open, and a different character for the wrong type of closer. ArrayDeque never stores null, so null can only mean "empty". The comparison top != c compares a Character with a char, so Java unboxes top and compares the characters by value.

Edge cases

• Empty string: valid.
• Odd length: always invalid. You can return false right away if s.length() % 2 == 1.
• Only one bracket type: a counter is enough (+1 for (, -1 for ), and the count must never go negative). With several types, the stack is needed to check the order.