#182 Delete Digits

题目描述：

Given string A representative a positive integer which has Ndigits, remove any k digits of the number, the remaining digits are arranged according to the original order to become a new positive integer.

Find the smallest integer after remove k digits.

N <= 240 and k <= N,

Have you met this question in a real interview?  Yes Example

Given an integer A = 

"178542"

, k = 

4

return a string 

"12"

题目思路：

这题要delete掉k个数，让剩下的数最小。那就换位思考一下，就是选A.length() - k个数，让选出来的数最小呗。这里需要注意的是，我们可以每次都选最小数，但是选的数必须在index = 0 ~ A.length() - k的范围内，不然下次可能就没的选了。

Mycode（AC = 14ms）：

class Solution {
public:
    /**
     *@param A: A positive integer which has N digits, A is a string.
     *@param k: Remove k digits.
     *@return: A string
     */
    string DeleteDigits(string A, int k) {
        // wirte your code here
        string ans = pickDigits(A, A.length() - k);
        
        while (ans.length() > 1 && ans[0] == '0'){
            ans = ans.substr(1);
        }
        
        return ans;
    }
    
    // 178542, 2
    string pickDigits(string A, int n) {
        if (A.length() == n) {
            return A;
        }
        else if (n == 0) {
            return "";
        }
        else {
            int rest_len = A.length() - n; // 4
            string min_num = A.substr(0, 1);
            int min_idx = 0;
            
            for (int i = 1; i <= rest_len; i++) { 
                if (A.substr(i, 1) < min_num) {
                    min_num = A.substr(i,1);
                    min_idx = i;
                }
            }
            
            //cout << min_num << " " << n << endl;
            if (min_idx + 1 < A.length()) {
                return min_num + pickDigits(A.substr(min_idx + 1), n - 1);
            }
            else {
                return min_num;
            }
        }
    }
};