Valid Parentheses

Easy Problem 33 of 151 Java and Python

Problem

Given a string s containing only the characters (, ), {, }, [ and ], decide whether it is valid.

It is valid when every open bracket is closed by a bracket of the same type, brackets close in the correct order, and every closing bracket has a matching open bracket.

Example 1

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

Example 2

Input: s = "([)]"
Output: false
Why: The ( is closed by ] before its own ).

Example 3

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

Constraints

1 ≤ s.length ≤ 10⁴
s contains only ()[]{}.

Explanation

The bracket that must close next is always the most recent unclosed one. "Most recent first" is exactly what a stack gives you.

Push open brackets. For a closing bracket, the top of the stack must be its partner; pop it. At the end, the stack must be empty.

Approach 1 · Naive

Remove matched pairs repeatedly

Time O(n²)
Space O(n)

A valid string always has an adjacent pair such as (). Keep deleting (), [] and {} until nothing changes; the string was valid if it is now empty.

Repeat: replace every "()", "[]" and "{}" with "".
Stop when the length no longer changes; return whether the string is empty.

Java

class Solution {
    public boolean isValid(String s) {
        int before;
        do {
            before = s.length();
            s = s.replace("()", "").replace("[]", "").replace("{}", "");
        } while (s.length() != before);
        return s.isEmpty();
    }
}

Python

class Solution:
    def isValid(self, s: str) -> bool:
        while True:
            shorter = s.replace("()", "").replace("[]", "").replace("{}", "")
            if shorter == s:
                return s == ""
            s = shorter

Approach 2 · Optimal

Stack of open brackets

Time O(n)
Space O(n)

Push each opening bracket. On a closing bracket, the stack top must be the matching opener.

Map each closer to its opener: ) → (, ] → [, } → {.
For an opener, push it. For a closer, if the stack is empty or its top is not the matching opener, return false; otherwise pop.
Return whether the stack is empty.

Java

import java.util.*;

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

Python

class Solution:
    def isValid(self, s: str) -> bool:
        pairs = {")": "(", "]": "[", "}": "{"}
        stack = []
        for c in s:
            if c in pairs:
                if not stack or stack.pop() != pairs[c]:
                    return False
            else:
                stack.append(c)
        return not stack

Complexity compared

Approach	Time	Space
Naive Remove matched pairs repeatedly	O(n²)	O(n)
Optimal Stack of open brackets	O(n)	O(n)

Key takeaways

Two classic slips: popping from an empty stack, and forgetting to check the stack is empty at the end (for input such as "((").
In Java, prefer ArrayDeque to the old Stack class.

Your notes

Saved in this browser as you type.

Solved it on your own?

Mark it done to track your progress, or star it to come back before an interview.

Next problem