How to Solve Valid Parentheses on LeetCode
Valid Parentheses is a classic stack-based problem for string validation.
Problem Statement
Given a string s containing just the characters '(', ')', '{', '}', '[' and ']', determine if the input string is valid. An input string is valid if:
Example:
Input: s = "()[]{}"
Output: true
Input: s = "(]"
Output: false
Why This Problem Matters for Interviews
- Tests stack data structure knowledge
- Commonly asked in phone screens and onsite interviews
- Prepares you for more advanced parsing questions
Approach to Valid Parentheses
Stack-Based Validation (Optimal)
Use a stack to keep track of opening brackets and match them with closing ones.
Time Complexity: O(n)
Space Complexity: O(n)
def isValid(s):
stack = []
mapping = {')': '(', '}': '{', ']': '['}
for char in s:
if char in mapping.values():
stack.append(char)
elif char in mapping:
if not stack or stack.pop() != mapping[char]:
return False
return not stack
Key Interview Talking Points
- Why stacks are ideal for nested structures
- Handling empty strings and unmatched brackets
- Difference between valid and balanced parentheses
Big O Complexity Recap
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Stack Method | O(n) | O(n) |
Pro Interview Tips
- Draw stack changes step by step
- Explain failure cases (extra closing/opening)
- Practice with deeply nested examples