C++ Greedy, O(N) Time O(1) Space


  • 0
    M

    In my algorithm I keep track of 3 values while traversing input string: psum is current sum of brackets (+1 for (, -1 for )), stars is current count of *, ssum is current sum of * converted to brackets. At every step we need to check that total balance psum + ssum is non-negative, ssum is kept minimal possible i.e. we greedily convert every * to ) thus ssum is minimal possible and always within range [-stars, +stars]. If ssum is too small and total balance becomes negative then we can increase ssum while it is within allowed bounds. At the end total balance should be 0 otherwise if it is positive it means we can't create balance through *'s because we greedily chosen ) for each * it means we kept lowest possible total balance at each step.

    class Solution {
    public:
        bool checkValidString(string const & s) {
            int psum = 0, stars = 0, ssum = 0;
            for (char c: s) {
                psum += c == '(' ? +1 : c == ')' ? -1 : 0;
                ssum -= c == '*';
                stars += c == '*';
                if (psum + ssum < 0) {
                    if (ssum >= stars) return false;
                    ++ssum;
                }
            }
            if (psum + ssum > 0) return false;
            return true;
        }
    };
    

Log in to reply
 

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