Valid String


  • 0

    Click here to see the full article post


  • 0
    S

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


  • 0
    Q

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


  • 0
    K

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


  • 0

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


  • 0
    R

    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"?


  • 0

    @robp Thanks, it was corrected.


  • 0
    L

    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)


  • 1
    M

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


  • 0
    R

    @m_scorpio In the article, he said:

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


  • 0
    H

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


  • 0
    M

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


  • 0
    D

    Wow this is so advanced.


  • 0

    @hhsu Thanks. It has been fixed.


  • 0
    N

    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)


  • 0
    S

    @nergi.r Can you post your DP solution?


  • 0
    M

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


  • 0
    K

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


  • 0
    N

    @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);
        }
    };
    

Log in to reply
 

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