Problem
A string contains only (), [] and {}. Return whether every opening bracket closes in reverse order.
Worked example
{[()]} is valid. ([)] fails when ) meets [.
Read {, [, and ( in that order. The most recent opener must close first, so ) removes (, ] removes [, and } removes {. For ([)], the first closer is ) while [ is still on top. Stop immediately.
How the solution works
The stack holds unmatched openers, with the most recent one on top. An empty stack at the end means no opening bracket remains.
Python stores opening brackets. Java stores the closing bracket it expects, so the two versions enforce the same order. Counting opening and closing brackets alone misses crossed pairs like ([)].
Python solution
def valid_brackets(text):
closing = {')': '(', ']': '[', '}': '{'}
stack = []
for char in text:
if char not in closing:
stack.append(char)
elif not stack or stack.pop() != closing[char]:
return False
return not stackJava solution
import java.util.ArrayDeque;
class Solution {
static boolean validBrackets(String text) {
var stack = new ArrayDeque<Character>();
for (char ch : text.toCharArray()) {
switch (ch) {
case '(': stack.push(')'); break;
case '[': stack.push(']'); break;
case '{': stack.push('}'); break;
default: if (stack.isEmpty() || stack.pop() != ch) return false;
}
}
return stack.isEmpty();
}
}Complexity and edge cases
O(n) time and O(n) space. Test the empty string, a leading closer, and unmatched opens.
Related exercise: Find the First Unique Character.
Comments
Post a Comment