Valid Parentheses
Check whether brackets are properly nested and closed. Every opening bracket must match a closing bracket of the same kind.
Work through the cases
3 examplesInput notation
One string containing only (), [], and {}.Expected result
true or false.Case 1
Input
{[()]}Expected output
true
Case 2
Input
([)]
Expected output
false
Case 3
Input
(
Expected output
false
These notes use simplified input/output notation. The linked platform defines the method signature and judge format.
FROM IDEA TO IMPLEMENTATION
Understand the approach.
Compare the documented approaches below. Brute force, better, and optimal versions appear where available; a direct exercise may need only one approach.
Repeatedly deleting adjacent pairs (), [], and \{\} until nothing is left is correct, but each pass rescans the string. With n ≤ 10^4, deeply nested input falls to O(n^2) and can easily time out. The bottleneck is that a match is more than two neighboring characters. A later opener must close first, while an earlier one stays open. Once the brackets cross, as in ([)], deleting neighbors cannot reduce the string to empty. Matching is therefore last-in, first-out: the only legal partner of the current closer is the most recent unmatched opener. A stack keeps those unfinished matches. An opener pushes its closer, so the closer allowed next sits on top, and a closer is compared only with that top. A mismatch means the type or the order is already wrong, and a non-empty stack at the end means some opener never closed.
We use a hash table d to map each opening bracket to its closing bracket, and a stack stk to store closers that have not been matched yet. Scan s from left to right. When the current character is an opening bracket, push the corresponding closer from d onto stk. When it is a closing bracket, return false if stk is empty or the popped top is different from that character.
After the scan, return true if stk is empty: every pair has been closed in the right type and order. If the stack still holds a closer, some opening bracket was never matched, so return false.
The time complexity is O(n), and the space complexity is O(n), where n is the length of s.
class Solution {
public boolean isValid(String s) {
Deque<Character> stk = new ArrayDeque<>();
Map<Character, Character> d = new HashMap<>(3);
d.put('(', ')');
d.put('[', ']');
d.put('{', '}');
for (char c : s.toCharArray()) {
if (d.containsKey(c)) {
stk.push(d.get(c));
} else if (stk.isEmpty() || stk.pop() != c) {
return false;
}
}
return stk.isEmpty();
}
}Reference code. Platform solutions may use supplied node types, imports, or collection libraries; foundational examples are complete programs.
Solutions adapted from Doocs / LeetCode contributors, licensed under CC BY-SA 4.0. Formatting changed; TypeScript versions converted to JavaScript. Supplemental implementations and approach notes added. Adapted solution material is available under the same license.