Given a string s containing only the characters ‘(’, ‘)’, ‘{’, ‘}’, ‘[’, and ‘]’, determine if the input string is valid. A string is valid if every opening bracket is closed by the same type of bracket, and brackets are closed in the correct order. Every closing bracket must have a corresponding opening bracket of the same type. An empty string is considered valid.
Example
s = "{[()]}"
Output: true
Every opening bracket has a matching closing bracket in the correct order: ( is closed by ), [ is closed by ], and { is closed by }.
Push every opening bracket onto a stack. When you encounter a closing bracket, check if the top of the stack is its matching opener — if not, the string is invalid. At the end, the stack should be empty for a valid sequence.
Why this works
Brackets must close in the reverse order they open – the most recent opener must be closed first. A stack naturally enforces this “last-in, first-out” order. Every time you see a closing bracket, you check that the top of the stack is the correct matching opener.
Step by step
- See an opening bracket — push it onto the stack.
- See a closing bracket — check if the stack’s top is the matching opener. If not (or stack is empty), it’s invalid.
- Pop on match — if they match, pop the opener off the stack and continue.
- Final check — after processing all characters, the stack must be empty. Leftover openers mean unmatched brackets.
Time: O(n)
Space: O(n)
class Solution {
public boolean isValid(String s) {
Deque<Character> stack = new ArrayDeque<>();
Map<Character, Character> matching = Map.of(
')', '(', ']', '[', '}', '{'
);
for (char c : s.toCharArray()) {
if (matching.containsKey(c)) { // it's a closing bracket
if (stack.isEmpty() || stack.peek() != matching.get(c)) {
return false;
}
stack.pop();
} else {
stack.push(c); // push opening brackets
}
}
return stack.isEmpty(); // valid only if all openers were matched
}
}
class Solution {
public:
bool isValid(string s) {
stack<char> st;
unordered_map<char, char> matching = {
{')', '('}, {']', '['}, {'}', '{'}
};
for (char c : s) {
if (matching.count(c)) { // it's a closing bracket
if (st.empty() || st.top() != matching[c]) {
return false;
}
st.pop();
} else {
st.push(c); // push opening brackets
}
}
return st.empty(); // valid only if all openers were matched
}
};
def isValid(s: str) -> bool:
stack = []
matching = {')': '(', ']': '[', '}': '{'} # maps each closer to its opener
for char in s:
if char in matching: # it's a closing bracket
if not stack or stack[-1] != matching[char]:
return False
stack.pop()
else:
stack.append(char) # push opening brackets
return not stack # valid only if all openers were matched