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 '*'.
- If at any point of time sm<0 we know its useless to proceed so return False.
- When we covered the entire string, return True if sm==0.
@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!