c, O(n) time recursive, mark and sweep solution


  • 0
    B
    static void removeKdigitsInt(char* num, int k) {
        char *p, *minp;
        if (k <= 0)
            return;
        if (k == strlen(num)) {
            memset(num, '#', k); /* mark as deleted. */
            return;
        }
        for (p = minp = num; *p && p - num <= k; p++)
            if (*minp > *p)
                minp = p;
        memset(num, '#', minp - num); /* mark as deleted. */
        removeKdigitsInt(minp + 1, k - (minp - num));
    }
    
    char* removeKdigits(char* num, int k) {
        char *p, *ind;
        
        if (k == strlen(num))
            return "0";
        
        removeKdigitsInt(num, k);
        
        /* sweep the marked digits */
        for (p = ind = num; *p; p++)
            if (*p != '#')
                *ind++ = *p;
        *ind = '\0';
        
        /* delete the leading zeroes */
        for (p = num; *p && *p == '0' && *(p + 1); p++);
        memmove(num, p, strlen(p) + 1);
        
        return num;
    }
    

Log in to reply
 

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