20. Valid Parentheses
## description
## 20. Valid Parentheses
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.
Example 1:
Input: s = "()"
Output: true
Example 2:
Input: s = "()[]{}"
Output: true
Example 3:
Input: s = "(]"
Output: false
Example 4:
Input: s = "([])"
Output: true
Example 5:
Input: s = "([)]"
Output: false
- –1 <= s.length <= 104
- –s consists of parentheses only '()[]{}'.
Constraints:
## notes
### Intuition
Brackets must close in the reverse order they were opened. A stack naturally enforces this LIFO property—each closing bracket should match the most recently opened one.
### Implementation
Use a map from opening to closing brackets. When encountering an opening bracket, push its expected closing bracket to the stack. When encountering a closing bracket, check if it matches the stack top—if so, pop and continue; if not (or stack is empty), return False.
### Edge-cases
Two important checks: the stack must be empty at the end (no unclosed brackets), and encountering a closing bracket when the stack is empty means there's no matching opener.
- –Time: O(n) — single pass through the string
- –Space: O(n) — stack can hold up to n/2 brackets
### Complexity
## solution
1
2class Solution:
3 def isValid(self, s: str) -> bool:
4 map = {
5 "(": ")",
6 "{": "}",
7 "[": ']',
8 }
9 stack = []
10 for c in s:
11 if c in map:
12 # opening bracket
13 stack.append(map[c])
14 else:
15 if len(stack) == 0 or stack[-1] != c:
16 return False
17 stack.pop()
18
19
20 return len(stack) == 0
21
22
23
24
25if __name__ == "__main__":
26 # Include one-off tests here or debugging logic that can be run by running this file
27 # e.g. print(solution.two_sum([1, 2, 3, 4], 3))
28 solution = Solution()
29