# Valid String

• Should not the DP solution's runtime complexity be O(n^3), because of the innermost for loop (k=i+1...)?

• I didn't get the idea of approach #3, can you explain it with more detail?

• Could you explain the intuition in approach #3? I don't quite understand.

• @qfai @kk636 Thanks. Please see the improved explanation for Approach #3.

• If we encounter a left bracket (c == '('), then lo++, otherwise we could write a right bracket, so lo--. If we encounter what can be a left bracket (c != ')'), then hi++, otherwise we could write a left bracket, so hi--

Shouldn't that be "must write a right bracket"?

• @robp Thanks, it was corrected.

• Empty string is also a possibility, so it is better to change the text "For each asterisk, let's try both possibilities". (Code is correct)

• The example for Approach #3 confused me. If we encounter , should lo-- & hi++?
[1, 2, 3] for '(
*'
Why not [0,1,2,3]?

• @m_scorpio In the article, he said:

[0, 1, 2] for '(*'; [1, 2, 3] for '(**';

• #2 does not work for input "*()"

• @robp

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

• Wow this is so advanced.

• @hhsu Thanks. It has been fixed.

• For dynamic programming approach, there exists a top-down 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_count-1)
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)

• @nergi.r Can you post your DP solution?

• You could also do greedy twice, once forwards treating all * as ( and once backwards treating all * as )

• Shouldn't it be [0,1,2,3] for '(**'?

• @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, cnt-1, memo);
ret = solve(s, pos+1, cnt, memo);
return ret = max(ret, max(solve(s, pos+1, cnt+1, memo), solve(s, pos+1, cnt-1, memo)));
}

bool checkValidString(string s) {
vector<vector<int> > memo(s.size(), vector<int>(500, -1));
return solve(s, 0, 0, memo);
}
};
``````

• How do you handle the case where * is an empty string?

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