Sharing my simple O(n) time O(1) space C++ solution


  • 0
    T

    The idea is to treat '*' as 'credits'.
    In the first pass, scan left to right, treat '*' as credit to '('.
    In the second pass, scan right to left, treat '*' as credit to ')'.

    bool checkValidString(string s) {
    if ( s.length() == 0 ) return true;

        int l = 0, r = 0, c = 0; 
        bool left = true;
        for(char& ch : s) {
            if ( ch == '(') l++;
            else if ( ch == ')') r++;
            else c++;
            if ( l+c < r ) { left = false; break; }
        }
        
        l = 0, r = 0, c = 0;
        bool right = true;
        for(int i = s.length()-1; i>=0; i-- ) {
            char ch = s[i];
            if ( ch == '(') l++;
            else if ( ch == ')') r++;
            else c++;
            if ( r+c < l ) { right = false; break; }
        }
        
        return left&&right;
    }

Log in to reply
 

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