Clear Python solution with explanation and comments


  • 1

    ##Key idea
    We divide the number into N parts from the right to the left, and each part weighs 3 if possible. All the parts follow the same pattern of converting, so we want a helper method to do the work. Next we distribute the base words (aka "Thousand", "Million") to each part and combine them.

    This question has lots of edge cases, and it very hard to notice all of them before the tests.(:з」∠)

    def numberToWords(self, num):
        if num == 0:
            return "Zero"
            
        result = ""
        str_num = str(num)[::-1]
        # Divede the string into N parts, where len(each part) <= 3
        dividing_list = [str_num[i:i+3][::-1] for i in xrange(0, len(str_num), 3)]
        
        # Distribute the base according to the index of dividing_list
        base = ["", " Thousand ", " Million ", " Billion "]
        for i in range(len(dividing_list)):
            tem = self.convert_three_to_eng(dividing_list[i])
            result = tem + ("" if not tem else base[i]) + result
        
        # Avoide undesirable space
        return " ".join(result.split())
    
    
    def convert_three_to_eng(self, s):
        # Helper lists, pay attention to the index
        one = ["", "One", "Two", "Three", "Four", "Five", "Six", "Seven", "Eight", "Nine"]
        ten = ["Ten", "Eleven", "Twelve", "Thirteen", "Fourteen", "Fifteen", "Sixteen", "Seventeen", "Eighteen", "Nineteen"]
        ten_a = ["", "", "Twenty ", "Thirty ", "Forty ", "Fifty ", "Sixty ", "Seventy ", "Eighty ", "Ninety "]
        
        num = int(s)
        result = ""
        
        # Same like the roman numeral problem algorithm: from high base to the low base
        if num / 100 != 0:
            result = one[(num / 100)] + " Hundred "
        if (num % 100) / 10 == 1:
            result += ten[num % 10]
            return result
        else:
            result += ten_a[(num % 100) / 10] + one[num % 10]
            return result

Log in to reply
 

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