valid_parentheses.py

classSolution:
defisValid(self, s: str) ->bool:

# main idea:
# A Last-In-First-Out (LIFO) data structure 
# such as 'stack' is the perfect fit

iflen(s)==0:
returnTrue

valid_char= ['(', ')', '{', '}', '[', ']']

left_half= ['(', '[', '{']
right_half= [')', ']', '}']

# use a map/dictionary, which is more maintainable
another_half= {')': '(', '}':'{', ']':'['}

my_stack= []

forcharins:
ifcharnotinvalid_char:
returnFalse

# we see an opening parenthesis, we push it onto the stack
ifcharinleft_half:
my_stack.append(char)

# we encounter a closing parenthesis, we pop the last inserted opening parenthesis
ifcharinright_half:
iflen(my_stack) ==0:
returnFalse
# be careful: check if the pair is a valid match
elifanother_half[char] !=my_stack[len(my_stack)-1]:
returnFalse
else:
my_stack.pop()

iflen(my_stack) !=0:
returnFalse
else:
returnTrue