Valid Parentheses
Given a string `s` containing only the bracket characters `(`, `)`, `{`, `}`, `[`, and `]`, determine if the string is valid. A string is valid when every opening bracket is closed by the same type of bracket, and brackets are closed in the correct order — meaning the most recently opened bracket must be closed first. **Core Insight:** This is a classic stack problem. Whenever we see an opening bracket we push it onto the stack. Whenever we see a closing bracket we check whether the top of the stack holds the matching opener. If it does, we pop and continue; if it doesn't (or the stack is empty), the string is invalid. At the end, the stack must be empty for the string to be valid. **Algorithm:** Iterate through each character. Push openers. On a closer, peek the stack — if the top matches, pop; otherwise return false. Return `stack.isEmpty()` at the end. **Complexity:** Time O(n) — one pass. Space O(n) — worst case all openers pushed onto the stack.
Constraints
- •
1 ≤ s.length ≤ 10⁴ - •
s consists of parentheses only
def isValid(s: str) -> bool:
stack = []
mapping = {')': '(', '}': '{', ']': '['}
for char in s:
if char in mapping:
top = stack.pop() if stack else '#'
if mapping[char] != top:
return False
else:
stack.append(char)
return not stack