Problem
Given a string containing just the characters ( ) { } [ ], determine if the input string is valid. Open brackets must be closed by the same type and in the correct order.
Example
Input: "()[]{}"
Output: trueInput: "(]"
Output: falseSolution
Use a stack. Push opening brackets onto the stack. For each closing bracket, check if it matches the top of the stack.
def is_valid(s):
stack = []
pairs = {')': '(', ']': '[', '}': '{'}
for ch in s:
if ch in '([{':
stack.append(ch)
elif not stack or stack.pop() != pairs[ch]:
return False
return not stackfunction isValid(s) {
const stack = [];
const pairs = { ')': '(', ']': '[', '}': '{' };
for (const ch of s) {
if ('([{'.includes(ch)) stack.push(ch);
else if (stack.pop() !== pairs[ch]) return false;
}
return stack.length === 0;
}#include <stack>
#include <string>
using namespace std;
bool isValid(string s) {
stack<char> st;
for (char ch : s) {
if (ch == '(' || ch == '[' || ch == '{') st.push(ch);
else {
if (st.empty()) return false;
char t = st.top(); st.pop();
if ((ch == ')' && t != '(') || (ch == ']' && t != '[') || (ch == '}' && t != '{')) return false;
}
}
return st.empty();
}import java.util.Stack;
public boolean isValid(String s) {
Stack<Character> stack = new Stack<>();
for (char ch : s.toCharArray()) {
if (ch == '(' || ch == '[' || ch == '{') stack.push(ch);
else {
if (stack.isEmpty()) return false;
char t = stack.pop();
if ((ch == ')' && t != '(') || (ch == ']' && t != '[') || (ch == '}' && t != '{')) return false;
}
}
return stack.isEmpty();
}Complexity
- Time: O(n)
- Space: O(n)
Explanation
Stacks are perfect for matching pairs because they preserve order. Every open bracket gets pushed; every close bracket pops and verifies. If anything mismatches or the stack is empty when popping, the string is invalid.
Comments
Join the discussion. Got a question, found an issue, or want to share your experience?