Short Python, one O(n) and one RegEx


  • 17

    O(n) Solution

    Go through the digits from left to right, remove previous digits if that makes the number smaller (and if we still have to remove digits). Almost the same as the prep function from my solution to an earlier problem, which did basically the same except it maximized the number.

    def removeKdigits(self, num, k):
        out = []
        for d in num:
            while k and out and out[-1] > d:
                out.pop()
                k -= 1
            out.append(d)
        return ''.join(out[:-k or None]).lstrip('0') or '0'
    

    Regex Solution

    k times remove the leftmost digit followed by a smaller digit (or remove the last digit). Didn't think this would be fast enough, but it is :-)

    def removeKdigits(self, num, k):
        sub = re.compile('1[0]|2[01]|3[0-2]|4[0-3]|5[0-4]|6[0-5]|7[0-6]|8[0-7]|9[0-8]|.$').sub
        for _ in range(k):
            num = sub(lambda m: m.group()[1:], num, 1)
        return num.lstrip('0') or '0'

  • 0
    T

    Great solution! Thanks for sharing, I got stuck at the while loop at first. I was using "if" statement and couldn't get some of the test cases passed.
    My accepted C++ version, the idea is the same as your Python code:

    string removeKdigits(string num, int k) {
            string sol;
            if (k >= num.length()) return "0";
            
            // while the last number is larger than the new one, 
            // keep poping out the last number until a smaller one appears
            // e.g. 1234567890 k=3
            for (int i = 0; i < num.length(); i++){
                while (sol.length() != 0 && k > 0 && sol.back() > num[i]){
                    sol.pop_back();
                    k--;
                }
                sol.push_back(num[i]);
            }
            
            // for monotonically increasing string
            // discard the last k digits
            // e.g. 123456 k=3
            while (k != 0){
                k--;
                sol.pop_back();
            }
            
            // for sol with leading zeros
            // e.g. 10200 k=1
            while(sol[0] == '0') sol.erase(0,1);
            
            return sol.length() == 0 ? "0" : sol;
            
        }
    

  • 0
    L

    How about the test case, num = "100" k =1 , the expected result should be "10" rather than "0".


  • 0

    @larrywang2014 No, "0" is correct. Check out the problem's Example 2 again.


  • 2
    O

    May I ask why it works? I cannot find any intuitive explanation for such algorithm...


  • 0
    W

    Nice solution. Here's my C++ implementation.

    class Solution {
    public:
        string removeKdigits(string num, int k) {
            vector<char> stk;
    
            for (char c : num) {
                while (k && !stk.empty() && stk.back() > c) {
                    stk.pop_back();
                    k--;
                }
                stk.push_back(c);
            }
            while (k > 0) {
                k--;
                stk.pop_back();
            }
    
            auto p = stk.begin();
            while (p != stk.end() && *p == '0') p++;
    
            return p == stk.end() ? string("0") : string(p, stk.end());
        }
    };
    

  • 0
    K

    C++ version

    class Solution {
    public:
        string removeKdigits(string num, int k) {
            if(k>=num.size()) return "0";
            string res="";
            for(char c:num)
            {
                while(res.size()&&k&&res.back()>c)
                {
                    res.pop_back();
                    k--;
                }
                if(c!='0'||(res.size()&&res[0]!='0'))
                    res.push_back(c);
            }
            while(k-->0) res.pop_back();
            return res.size()?res:"0";
        }
    };

  • 0
    S
    This post is deleted!

  • 0

Log in to reply
 

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