Valid Parentheses
Problem
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 in the correct order.
Examples
Example 1
Input: s = "()"
Output: true
Example 2
Input: s = "()[]{}"
Output: true
Example 3
Input: s = "(]"
Output: false
Constraints
- •
1 <= s.length <= 10^4
Hints
Hint 1
A stack is the right structure specifically because bracket matching is LAST-IN-FIRST-OUT — the most recently opened bracket must be the next one closed. A queue (first-in-first-out) would match brackets in the wrong order.
Hint 2
Push every OPENING bracket. On a CLOSING bracket, the stack's top must be its matching opener — if it isn't (or the stack is empty), the string is invalid immediately.
Hint 3
A valid string must end with an EMPTY stack — a non-empty stack at the end means some opening bracket was never closed.
Solutions
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 top = stack.pop();
if (c == ')' && top != '(') return false;
if (c == ']' && top != '[') return false;
if (c == '}' && top != '{') return false;
}
}
return stack.isEmpty();
}Time: O(n) · Space: O(n)