Annotated greedy C+ solution


  • 0
    K
    string removeKdigits(string num, int k) {
        // the reasoning on weather the greedy solution works starts with an
        //  observation that removing _a_ vs. removing _b_ in the number
        //  "[.1.]a[.2.]b[.3.]" doesn't change blocks "[.1.]" and "[.3.]"
        // therefore the choice between eliminating _a_ vs. _b_ is made based
        //  on comparison of "[.2.]b" with "a[.2.]" or, equivalently, digit
        //  _a_ and the following digit from block "[.2.]" (consider no ties)
        // in other words we need to scan the _num_ from the most significant
        //  (left-most) side looking for sequential pairs _ab_ where _a_>_b_
        //  and drop _a_ until we exhaust _k_
    
        // check the trivial cases first
        if( num.size() <= k ) return "0";
        if( k <= 0 ) return num;
    
        // look for the first left-most case of decreasing _ab_ sequence
        for(int pos=0; pos<num.size()-1 && k>0; ){
            if( num[pos] > num[pos+1] ){
                num.erase(pos,1);
                pos = 0; // start over for simplicity
                k--;
            } else
                pos++;
        }
    
        // still need to delete something? chop "biggest" digits from the tail
        num.erase( num.size()-k, k );
    
        // drop leading zeros
        int pos = 0;
        for(; pos<num.size() && num[pos] == '0'; pos++);
        if( pos ) num.erase(0,pos);
    
        // yet another trivial case
        if( num.size() == 0 ) return "0";
    
        return num;
    }

Log in to reply
 

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