# Intuition\nFirst think about Recursive solution. On the very high level building recursive solution is easy.. Whenever we will face `*` then we have three choices. Add an `opening bracket` or `closing bracket` or `add nothing`. Now lets build the intuition\n\n# Approach\n\nwhenever you will face an opening bracket then count of opening bracket will increase by 1 and for closing bracket the count of opening bracket will decrease by 1.\n\nFinally at the end of the string opening bracket count has to be 0 to be a valid parenthesis string.\n\n# Here an edge case.. \n**Decreasing opening bracket count by 1 when we face a closing bracket states that a closing bracket counters/closes an opening bracket. but if opening bracket count is 0 that means there is no opening bracket to counter/close. \nSo we will only decrease opening bracket count by 1 when we will face a closing bracket and opening bracket count is not zero.**\n\n# Now our recursive solution will build up.\n\nThe base case is -> if index reaches end of the string then we will return true if opening bracket count is 0 (Means all opening bracket has been closed by a closing bracket) else we will return false.\n\nAnd if the `s[ind]` is not a `*`.\n- Then if `s[ind] == opening bracket \'(\'` then opening bracket count will increase by 1 and move to `ind+1`\n- And if `s[ind] == closing bracket \')\'` then opening bracket count will decrease by 1 if opening bracket count is not 0 and move to `ind+1`\n\nAnd if the `s[ind]` is a `*`\n- Then we can add a opening bracket means opening bracket count will increase by 1 and move to `ind+1`.\n- Or we can add a closing bracket means opening bracket count will decrease by 1 if opening bracket count is not 0 and move to `ind+1`\n- Or we don\'t add anything means opening bracket count will remain same and move to `ind+1`\n```\n// Recursive Solution\nclass Solution {\n bool ex(int ind, int openingBracket, string &s){\n if(ind==s.size()) return (openingBracket==0);\n\n bool ans=false;\n if(s[ind]==\'*\'){\n ans|=ex(ind+1,openingBracket+1,s); // Add \'(\'\n if(openingBracket) ans|=ex(ind+1,openingBracket-1,s); // Add \')\'\n ans|=ex(ind+1,openingBracket,s); //Add Nothing\n }else{\n if(s[ind]==\'(\'){\n ans=ex(ind+1,openingBracket+1,s);\n }else{\n if(openingBracket) ans=ex(ind+1,openingBracket-1,s);\n }\n }\n\n return ans;\n }\n\npublic:\n bool checkValidString(string s) {\n return ex(0,0,s);\n }\n};\n```\n\n# Complexity\n- Time complexity:\n\n`O (3 ^ n)` This recursive solution will give you TLE because `3 ^ 100` is huge\n\n- Space complexity:\n\n`O (1)`\n\n# Now convert Recursive solution to Memoization.\nwe have to memoize the recursive solution using a DP table. Becase there are so many repetition.\n\nOur DP table will store true or false means if the string is valid for every possible combination of index and opening bracket count.\nSo lets cache the calculated state in the DP table. And for every iteration just check if the current states are already calculated or not. If it\'s then directly return the value from DP table.\n```\n// Memoization\nclass Solution {\n bool ex(int ind, int openingBracket, string &s, vector> &dp){\n if(ind==s.size()) return (openingBracket==0);\n\n if(dp[ind][openingBracket]!=-1) return dp[ind][openingBracket];\n\n bool ans=false;\n if(s[ind]==\'*\'){\n ans|=ex(ind+1,openingBracket+1,s,dp);\n if(openingBracket) ans|=ex(ind+1,openingBracket-1,s,dp);\n ans|=ex(ind+1,openingBracket,s,dp);\n }else{\n if(s[ind]==\'(\'){\n ans=ex(ind+1,openingBracket+1,s,dp);\n }else{\n if(openingBracket) ans=ex(ind+1,openingBracket-1,s,dp);\n }\n }\n\n return dp[ind][openingBracket]=ans;\n }\n\npublic:\n bool checkValidString(string s) {\n vector> dp(s.size(), vector(s.size(),-1));\n return ex(0,0,s,dp);\n }\n};\n```\n\n# Complexity\n- Time complexity:\n\n`O (n ^ 2) + Recursion stack space` \n\n- Space complexity:\n\n`O (n * n)`\n\n# Now convert Memoization to Tabulation.\n\nTabulation means run loop for checking every changing parameters. Here is only two changing parameters. One is index and another one is opening bracket count. so run two loop to go through every possibilities. \n\n**Now copy the base case from recursive solution/memoization**\n\n- `if(ind==s.size()) return (openingBracket==0);`\nMeans `dp[s.size()][0] = true` states that at the end of the string opening bracket count has to be 0 to be a valid parenthesis string.\n\n**Now copy the recurrence**\n- Our answer will be stored in `dp[0][0]` states that we will check every combination of index and opening bracket count by two for loops. One for index and one for opening bracket count. \nAfter traversing the whole string if at `dp[0][0] == true` means It is possible to make a way where after traversing the whole string our opening bracket count will be 0 (Valid parenthesis).\n```\n// Tabulation\nclass Solution {\npublic:\n bool checkValidString(string s) {\n vector> dp(s.size()+1, vector(s.size()+1,0));\n dp[s.size()][0]=1;\n\n for(int ind=s.size()-1; ind>=0; ind--){\n for(int openingBracket=0; openingBracket\n`O (n ^ 2)`\n\n- Space complexity:\n\n`O (n * n)`\n\n# Pleaseeeeeeeeeeeeeeeeeeeee UPVOTE\n![2roca1.jpg](https://assets.leetcode.com/users/images/7acee8c3-2878-4b8c-a343-f09637b5a43b_1678780243.426397.jpeg)\n

Valid Parenthesis String

Problem Description

Problem Description

Answer Panel