 # 20. Valid Parentheses

Updated: 2023-09-01 LeetCode 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


## First accepted

Idea:

1. Loop through string
2. If current “closes” the last in stack, then remove last from stack
3. Else: add current to stack
class Solution:
def isValid(self, s: str) -> bool:
stack = []
par_dict = {'(': ')', '{': '}', '[': ']'}
last_value = None
for i in s:
second_value = par_dict.get(last_value, None)
if i == second_value:
stack.pop()
last_value = stack[-1] if stack else None
else:
stack.append(i)
last_value = i
return not stack


## Better solution

class Solution:
def isValid(self, s: str) -> bool:
par_dict = {'(': ')', '{': '}', '[': ']'}
stack = []
for char in s:
if char in par_dict:   # If it's an opening bracket, add it to the stack
stack.append(char)
elif stack: # If there's something in the stack
if char == par_dict[stack[-1]]:
# If it's a closing bracket for the last opened bracket, remove it from the stack.
stack.pop()
else:   # It's not a closing bracket for the last opened bracket. Invalid string.
return False
else:   # Not an opening bracket or closing bracket. Invalid string.
return False
return stack == []