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

• ``````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.

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

• @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!

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