Easy understanding java recursive solution with detailed explanation

  • 0

    kernel idea is to find the minimum number in the num string,

    [m,i,n]: i is the index of minimum letter, there are m letters before i, and n letters after i.

    if(m>=k): we need to recursively remove k letters from m and append with [i,n]. e.g. "34512" with k=2, the result is removeKdigits("345",2)+"12"

    if(m<k): we remove all m and remove k-m letters from n, the result is i+ recursive result. e.g.: "31254" with k=2, the result is "1"+ removeKdigits("254",2)

    some corner case:

    • length ==k : return "0"

    • if from 0 to k index, there is a '0' at j, we remove [0,j] and recursively remove the [j+1,length] with k=k-j, because we can remove one more letter( '0'), the result must be smaller than not). e.g.:"107069" with k=2, first remove "10", then remove"70", so the result is "69", we remove two more letters.

    • after recursion, we need to ensure there's no '0' at the front of the result. e.g. "312" with k=1, we will get result by calling removeKdigits("3",1)+"12", it will return "012", so we should remove the "0"

    public String removeKdigits(String num, int k) {
            int minIndex=0;
            char min='9';
            int len=num.length();
            if(k==len) return "0";
            if(k==0) return num;
            for(int i=0;i<num.length();i++){ //find the minimun number in the string
                    return removeKdigits(num.substring(i+1),k-i);
                return ""+min;
            String r="";
            int i=0;
            return r.substring(i);

Log in to reply

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