Java Greedy Solution Accepted


  • 0

    This is a recursive solution. First, find the minimum digit within range[0, k]. determine how many digit to delete in order to make it the first digit. Retain that digit, recursive find the minimum number behind it.

    public class Solution {
        public String removeKdigits(String num, int k) {
            String result = helper(num, k);
            int i = 0;
            while (i < result.length()-1) {
                if (result.charAt(i) != '0') break;
                i++;
            }
            result = result.substring(i, result.length());
            if (result.length() == 0) return "0";
            return result;
        }
        
        private String helper(String num, int k) {
            if (num.length() <= k) return "";
            if (k == 0) return num;
            char min = num.charAt(0);
            int minIndex = 0;
            for (int i = 1; i <= k; i++) {
                if (num.charAt(i) < min) {
                    min = num.charAt(i);
                    minIndex = i;
                }
            }
            String num2 = helper(num.substring(minIndex+1, num.length()), k-minIndex);
            return num.charAt(minIndex)+num2;
        }
    }

  • 0
    A
    This post is deleted!

  • 0
    H

    Could you explain your code more? Why it works?


Log in to reply
 

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