Valid Parentheses

Given a string s containing just the characters '(', ')', '{', '}', '[' and ']', determine if the input string is valid. An input string is valid if open brackets are closed by the same type of bracket, open brackets are closed in the correct order, and every closing bracket has a corresponding open bracket of the same type.

Test Case 1:

Input:s = "()"

Output:true

Explanation:A single matching pair.

Test Case 2:

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

Output:true

Explanation:Three separate pairs, each opened and closed before the next begins.

Test Case 3:

Input:s = "(]"

Output:false

Explanation:The bracket types don't match — '(' can only be closed by ')'.

Constraints

◆1 ≤ s.length ≤ 10⁴
◆s consists only of the characters '(', ')', '{', '}', '[' and ']'

🚀

Try the Dry Run

Don't just read the solution — watch it execute, one step at a time.

🧪Try your own test case

s (string) — 1-20 characters: ( ) { } [ ]

1	class Solution {
2	public boolean isValid(String s) {
3	Deque<Character> stack = new ArrayDeque<>();
4	Map<Character, Character> pairs = Map.of(')', '(', '}', '{', ']', '[');
5	for (char c : s.toCharArray()) {
6	if (c == '(' \|\| c == '{' \|\| c == '[') {
7	stack.push(c);
8	} else {
9	if (stack.isEmpty() \|\| stack.pop() != pairs.get(c)) return false;
10	}
11	}
12	return stack.isEmpty();
13	}
14	}
15

String

{

[

(

)

]

}

Stack

empty

INITIALIZE

Create an empty stack. We'll push every opening bracket we see, and pop to check closing brackets against it.

Step 1 / 17

Approach & Solutions

Brute Force — Repeated Removal

Brute

Repeatedly scan the string for an adjacent matching pair — "()", "{}", or "[]" — and remove it, shrinking the string. If the string can be whittled all the way down to empty, every bracket had a partner in the right place. Each pass is O(n), and up to n/2 passes may be needed, so this costs O(n²) overall.

TimeO(n²)

SpaceO(n)

Java

Try it out

class Solution {
    public boolean isValid(String s) {
        while (s.contains("()") || s.contains("{}") || s.contains("[]")) {
            s = s.replace("()", "").replace("{}", "").replace("[]", "");
        }
        return s.isEmpty();
    }
}

Optimal — Stack

Optimal

Walk through the string once. Every opening bracket gets pushed onto a stack. Every closing bracket must match whatever is currently on top of the stack — if it does, pop it and move on; if it doesn't (or the stack is empty), the string is invalid immediately. At the end, the string is valid only if the stack is empty — every opener found its closer, in the right order.

TimeO(n)