Valid String




@robp
Oh, thanks for your correction.What I am really confused is:
If we encounter*
, should lo & hi++?
[1, 2, 3] for '(**'
why not [0,1,2,3]?In fact, I copied it same as you, but it changed after submission. So sorry for not dealing with the format properly...


For dynamic programming approach, there exists a topdown dp with O(N^2) time.
The state is [current_pos][balance_count]
At every state, if s[current_pos] is '(', recursive to (current_pos+1, balance_count+1)
else if s[current_pos] is ')', recursive to (current_pos+1, balance_count1)
else treat the '*' as either nothing (current_pos+1, balance_count) or any of the parantheses.
This way, you will have at most 3 transitions and 2 states.
Hence, the total complexity would be O(n^2)


@shafiul Here it is
class Solution { public: int solve(string &s, int pos, int cnt, vector<vector<int>> &memo) { if(cnt<0) return 0; if(pos==s.size()) return (cnt==0); int &ret = memo[pos][cnt+100]; if(ret!=1) return ret; if(s[pos]=='(') return ret = solve(s, pos+1, cnt+1, memo); else if(s[pos]==')') return ret = solve(s, pos+1, cnt1, memo); ret = solve(s, pos+1, cnt, memo); return ret = max(ret, max(solve(s, pos+1, cnt+1, memo), solve(s, pos+1, cnt1, memo))); } bool checkValidString(string s) { vector<vector<int> > memo(s.size(), vector<int>(500, 1)); return solve(s, 0, 0, memo); } };