LC 0678 [M] Valid Parenthesis String - ALawliet/algorithms GitHub Wiki
start with checking the right first and allow a left or wildcard to pair it
https://www.youtube.com/watch?v=2ef4_2R4rg8
class Solution:
def checkValidString(self, s: str) -> bool:
# what makes a string invalid?
# 1. we have too many right tokens. not enough left/wild to pair
leftWild = 0
left = 0
for c in s:
# making sure all our right tokens have a pair
if c == ')':
if leftWild == 0: return False
leftWild -= 1
else:
leftWild += 1
# making sure all our left tokens have a pair
if c == '(':
left += 1
else:
left = max(0, left - 1)
return left == 0