Simple Python DP solution using Counter


  • 0
    A
    class Solution(object):
        def checkValidString(self, s):
            """
            :type s: str
            :rtype: bool
            """
            m = len(s)
            if m == 0: return True
            f = [set() for i in xrange(m + 1)]
            f[0].add(0)
            for i in xrange(1, m + 1):
                for v in f[i-1]:
                    if s[i-1] == '(':
                        f[i].add(v + 1)
                    elif s[i-1] == ')':
                        if v - 1 >= 0:
                            f[i].add(v-1)
                    else:
                        f[i].add(v + 1)
                        if v - 1 >= 0:
                            f[i].add(v - 1)
                        f[i].add(v)
            return 0 in f[m]
    

Log in to reply
 

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