678. Valid Parenthesis String

'''
Given a string s containing only three types of characters: '(', ')' and '*', return true if s is valid.

The following rules define a valid string:

Any left parenthesis '(' must have a corresponding right parenthesis ')'.
Any right parenthesis ')' must have a corresponding left parenthesis '('.
Left parenthesis '(' must go before the corresponding right parenthesis ')'.
'*' could be treated as a single right parenthesis ')' or a single left parenthesis '(' or an empty string "".
Constraints:
1 <= s.length <= 100
s[i] is '(', ')' or '*'.
'''
#Method 2:O(n)
'''
position of * is important . For e,g, (* is true but *( is False.Hence we shall keep two stacks and store the indices one
for the stars and other for open braces.
Now when ever we get open brace or * we append them to respective stack.
Incase of ')' we shall pop open stack if not empty else we check if there is any * then we shall pop.
If both stacks seems to be empty then this closing brace cant be matched.Hence return False.
After iterating the string now check whether open is empty or not. If its not empty we need to find respective closing
braces using the star stack. For a match to happend we should find a star whose index is greater than open brace index.
Watch techdose vidoe if you dont understand
'''
class Solution:
    def checkValidString(self, s: str) -> bool:
        n=len(s)
        star=[]
        op=[]
        for i in range(n):
            if s[i]=='(':
                op.append(i)
            elif s[i]=='*':
                star.append(i)
            else:
                if op:
                    op.pop()
                elif star:
                    star.pop()
                else:
                    return False
        #print(op,star)
        while op and star:
            if op[-1]<star.pop():
                op.pop()
        if op:return False
        return True


#Method 1:O(n**3) Dp
class Solution:
    def checkValidString(self, s: str) -> bool:
        n=len(s)
        @cache
        def dfs(i,dif):
            if i==n:return dif==0
            if dif<0:return False
            if s[i]=='(':
                return dfs(i+1,dif+1)
            elif s[i]==')':
                return dfs(i+1,dif-1)
            else:
                return dfs(i+1,dif+1) or dfs(i+1,dif-1) or dfs(i+1,dif)
        return dfs(0,0)