Valid Parentheses
LeetCode #20 · Easy · Stack & Queue · C++ solution with worked-out approach and complexity analysis.
Approach
Stack
Use a stack to keep track of opening brackets. When a closing bracket is encountered, check if the stack is empty or if the top of the stack matches the corresponding opening bracket. If valid, pop from stack. Finally, check if stack is empty.
Time
O(n)
Space
O(n)
Problem description(from LeetCode)
Given a string s containing just the characters '(', ')', '{', '}', '[' and ']', determine if the input string is valid. An input string is valid if: 1. Open brackets must be closed by the same type of brackets. 2. Open brackets must be closed in the correct order. 3. Every close bracket has a corresponding open bracket of the same type.
Examples
Example 1
- Input:
- s = "()"
- Output:
- true
Constraints
- •1 <= s.length <= 10^4
- •s consists of parentheses only '()[]{}'.
C++ Solution
solution.cpp
class Solution {
public:
bool isValid(string s) {
stack<char> st;
unordered_map<char, char> um = {{'(', ')'}, {'[', ']'}, {'{', '}'}};
for (int i = 0, n = s.size(); i < n; i++) {
if (s[i] == '(' || s[i] == '[' || s[i] == '{') {
st.push(s[i]);
} else {
if (st.empty() || um[st.top()] != s[i]) return false;
st.pop();
}
}
return st.empty();
}
};