Python, Simple DP (Top Down) solution (With Explanation)


  • 0
    P
    class Solution:
        def checkValidString(self, s):
            dp = [[-1]*(len(s)+1) for _ in range(len(s))]
            def dfs(i,sm):
                if i==len(s):
                    return sm==0
                if dp[i][sm]!=-1: return dp[i][sm]
                if sm<0: return False
                if s[i]=='(': t1 = dfs(i+1,sm+1)
                elif s[i]==')': t1 = dfs(i+1,sm-1)
                elif s[i]=='*': t1 = dfs(i+1,sm) or dfs(i+1,sm+1) or dfs(i+1,sm-1)
                dp[i][sm] = t1
                return t1
            return dfs(0,0)
    

    Intuition: For each * encountered we can try all the three possibilities i.e. take it as a '(' (sm+1), ')' (sm-1), ''(sm).
    There could be overlapping subproblems with respect to the the index i of the string with the sm encountered at that index. So just memorize the values for each i,sm encountered.
    sm variable stores the cumulative sum i.e +1 for '(',
    -1 for ')' and 0,+1,-1 for '*'.
    Base Case:

    1. If at any point of time sm<0 we know its useless to proceed so return False.
    2. When we covered the entire string, return True if sm==0.

  • 0

    Same here. for complexity, I think the worst case is O(n^3). Am I right?


  • 0
    P

    @roc571 No its O(n^2), check the dimensions of the dp array.
    For each index of the string we can associate values for atmost n states (here n is the maximum value of the sm variable). So n^2.
    Hope it helps!


Log in to reply
 

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