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
                if(i<=k&&num.charAt(i)=='0'){
                    return removeKdigits(num.substring(i+1),k-i);
                }
                if(num.charAt(i)<min){
                    min=num.charAt(i);
                    minIndex=i;
                }
            }
            if(k==len-1){
                return ""+min;
            }
            String r="";
            if(minIndex>=k){
                r=removeKdigits(num.substring(0,minIndex),k)+num.substring(minIndex);
            }else{ 
                r=num.charAt(minIndex)+removeKdigits(num.substring(minIndex+1),k-minIndex);
            }
            int i=0;
            
            for(;i<r.length()&&r.length()>1;i++){
                if(r.charAt(i)!='0'){
                    break;
                }
            }
            return r.substring(i);
        }
    

Log in to reply
 

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