Stack
Intuition
A stack is the perfect data structure for matching brackets because it follows a Last-In-First-Out (LIFO) order, which mirrors how nested brackets work -- the most recently opened bracket must be the first one closed. When we encounter an opening bracket, we push it onto the stack. When we encounter a closing bracket, we check if it matches the top of the stack (the most recent unmatched opening bracket). If it matches, we pop the stack and continue. If it does not match, or the stack is empty when we see a closing bracket, the string is invalid. At the end, the string is valid only if the stack is empty (all brackets matched).
Algorithm
- Create a mapping of closing brackets to their corresponding opening brackets for quick lookup.
- Initialize an empty stack.
- Iterate through each character in the string.
- If the character is an opening bracket ( '(', '[', '{' ), push it onto the stack.
- If the character is a closing bracket, check if the stack is non-empty and the top element matches the corresponding opening bracket.
- If it matches, pop the top of the stack. If it does not match or the stack is empty, return false.
- After processing all characters, return true if the stack is empty, false otherwise.
Time
O(n)SpaceO(n)Code (C++ · Java · Python · Go)
class Solution {
public:
bool isValid(string s) {
stack<char> st;
unordered_map<char, char> map = {
{')', '('},
{']', '['},
{'}', '{'}
};
for (char c : s) {
if (map.count(c)) {
if (st.empty() || st.top() != map[c]) {
return false;
}
st.pop();
} else {
st.push(c);
}
}
return st.empty();
}
};class Solution {
public boolean isValid(String s) {
Deque<Character> stack = new ArrayDeque<>();
Map<Character, Character> map = Map.of(
')', '(',
']', '[',
'}', '{'
);
for (char c : s.toCharArray()) {
if (map.containsKey(c)) {
if (stack.isEmpty() || !stack.peek().equals(map.get(c))) {
return false;
}
stack.pop();
} else {
stack.push(c);
}
}
return stack.isEmpty();
}
}def isValid(s: str) -> bool:
stack = []
mapping = {")": "(", "]": "[", "}": "{"}
for char in s:
if char in mapping:
if not stack or stack[-1] != mapping[char]:
return False
stack.pop()
else:
stack.append(char)
return len(stack) == 0func isValid(s string) bool {
stack := []rune{}
pairs := map[rune]rune{')': '(', '}': '{', ']': '['}
for _, ch := range s {
if ch == '(' || ch == '{' || ch == '[' {
stack = append(stack, ch)
} else {
if len(stack) == 0 || stack[len(stack)-1] != pairs[ch] {
return false
}
stack = stack[:len(stack)-1]
}
}
return len(stack) == 0
}