Brief Python with Brief Explanation


  • 0
    S
    """It is easy to prove "optimally remove k chars == optimally remove 1 char k times sequentially". As an example, we prove remove 2 (l1 and l2) == remove 1 (k1) and then remove 1 (k2).
    1) By definition, left <= right
    2) remove(l1, l2) >= remove (k1, l2) [from the optimality of k1] >= remove(k1, k2) [from optimality of k2]. So left >= right
    """
    def removeKdigits(self, num, k):
        """
        :type num: str
        :type k: int
        :rtype: str
        """
        def round(n, _):
            try:
                i = next(j for j in range(len(n) - 1) if n[j] > n[j + 1])
                n = n[:i] + n[i + 1:]
            except:
                n = n[:-1]
            return n.lstrip('0').zfill(1)
    
        return reduce(round, range(k), num)

Log in to reply
 

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