> [!META]- Inline Metadata
> [tags:: #career #leetcode/stacks]
> [project group:: Neetcode 150]
> [difficulty:: easy]
> [status:: done]
> [link:: https://leetcode.com/problems/valid-parentheses/]
> [up:: [[Leetcode MOC]]]
## Problem
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`
**Constraints:**
- `1 <= s.length <= 104`
- `s` consists of parentheses only `'()[]{}'`.
## Solution
### Mine
#### Python
```python
def isValid(self, s: str) -> bool:
stack = []
close_to_open = {
")": "(",
"}": "{",
"]": "["
}
for char in s:
if opener := close_to_open.get(char):
if stack and stack[-1] == opener:
stack.pop()
else:
return False
else:
stack.append(char)
if stack:
return False
else:
return True
```
#### Rust
### LC's
## Things I Learned
## Scratchpad
In Python, you can use a List as a stack, just by using `.append()` and `.pop()`.
Incorrect order is something like this: `([)]`
Must start with an opening brace of some sort.
As we add closing parentheses, we have to remove the opening one as well, which is a hint for a stack. Once removing the closing brace, then popping the next item should be the opening brace, this has to do with the "correct order" constraint.
**Use a hashmap to match closing brace against opening**
### Structure
- Set up empty list + close_to_open hashmap
- Iterate through string
- if character is in `close_to_open`
- check if stack isn't empty and that the final value on the stack is the correct opening brace (the stack is added to in reverse order)
- if so: pop
- if not, return `False`
- if character isn't, then it's an opening brace and we add it to the stack
- After iteration, if stack is back to being empty, return `True`, else `False`