Simple Python Solution with DP


  • 0
    Z
    def checkValidString5(s):
            """
            :type s: str
            :rtype: bool
            """
            #dp = []
            # if using list, there are a lot of duplicates
            # using set could make if much faster
            prev=set()
            prev.add((0,0))
            for i in range(len(s)):
                temp = set()
                for elem in prev:
                    if s[i]=='(':
                        temp.add((elem[0]+1,elem[1]))
                    elif s[i]==')':
                        if elem[0]>=elem[1]+1:
                            temp.add((elem[0],elem[1]+1))
                    else:
                        if elem[0]>=elem[1]+1:
                            temp.add((elem[0],elem[1]+1))
                        temp.add((elem[0],elem[1]))
                        temp.add((elem[0]+1,elem[1]))
                if len(temp)==0:
                    return False
                prev = temp
                #print(prev)
            for elem in prev:
                #print(elem)
                if elem[0]==elem[1]:
                    return True
            else:
                return False

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.