Python recursive and iterative solutions


  • 1
    C

    First, I tried recursive solution, but I got memory limited exceeded for long string and large k value

        def removeKdigits(self, num, k):
            # memory limite exceed for recursive
            if k == 0 or num == '': return num if num else '0'
            i = 0
            while i+1 < len(num) and int(num[i+1]) >= int(num[i]):
                i += 1
            return self.removeKdigits(num.replace(num[i],'', 1).lstrip('0'), k-1)
    

    Then, I tried iterative solution, with the complexity of O(kn)

        def removeKdigits(self, num, k):
            while k > 0  and num:
                j = 0
                while j+1<len(num) and num[j+1] >= num[j]:
                    j += 1
                num = num.replace(num[j],'',1).lstrip('0')
                k -= 1
            return num or '0'
    

    Then I realized that I can do it with O(n) complexity but requiring O(n) space

        def removeKdigits(self, num, k):
            ret = []
            for i in num:
                while k > 0 and ret and ret[-1] > i:
                    ret.pop()
                    k -= 1
                ret.append(i)
            if k != 0: ret = ret[:len(ret)-k]
            ret = ''.join(ret).lstrip('0')
            return ret if ret else '0'
    

  • 0

    The middle one doesn't work. (now does)


  • 0
    C

    thanks. It should be

     while i < k and num:
    

    updated


  • 0

    Two possible improvements for it:

    • count down k instead of using i
    • return num or '0'

  • 0
    C

    @StefanPochmann thank you for the tips. updated


Log in to reply
 

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