Convert a non-negative integer to its english words representation. Given input is guaranteed to be less than 231 - 1.

Example 1:


Input: 123
Output: "One Hundred Twenty Three"


Example 2:


Input: 12345
Output: "Twelve Thousand Three Hundred Forty Five"

Example 3:


Input: 1234567
Output: "One Million Two Hundred Thirty Four Thousand Five Hundred Sixty Seven"


Example 4:


Input: 1234567891
Output: "One Billion Two Hundred Thirty Four Million Five Hundred Sixty Seven Thousand Eight Hundred Ninety One"

Difficulty: interview

Starter code:

class Solution:
    def numberToWords(self, num: int) -> str:
        

Solutions:
class Solution:
     V1 = ["", "One", "Two", "Three", "Four", "Five", "Six", "Seven", "Eight", "Nine", "Ten",
           "Eleven", "Twelve", "Thirteen", "Fourteen", "Fifteen", "Sixteen", "Seventeen", "Eighteen", "Nineteen"]
     V2 = ["", "", "Twenty", "Thirty", "Forty", "Fifty", "Sixty", "Seventy", "Eighty", "Ninety"]
     V3 = ["Thousand", "Million", "Billion"]
 
     def numberToWords(self, num):
         """
         :type num: int
         :rtype: str
         """
         if num == 0:
             return "Zero"
         
         answer = self.convert_hundred(num % 1000)
         for i in range(3):
             num //= 1000
             
             if num % 1000 > 0:
                 following = " " + answer if answer else ""
                 answer = self.convert_hundred(num % 1000) + " " + self.V3[i] + following
 
         return answer
 
     def convert_hundred(self, num):
         answer = ""
         
         a = num // 100
         b = num % 100
         c = num % 10
         
         if b < 20:
             answer = self.V1[b]
         else:
             following = " " + self.V1[c] if c > 0 else ""
             answer = self.V2[b // 10] + following
         
         if a > 0:
             following = " " + answer if answer else ""
             answer = self.V1[a] + " Hundred" + following
         
         return answer


class Solution:
     def parseHundred(self, n):
         to19 = 'One Two Three Four Five Six Seven Eight Nine Ten Eleven Twelve Thirteen Fourteen Fifteen Sixteen Seventeen Eighteen Nineteen'.split()
         tens = 'Twenty Thirty Forty Fifty Sixty Seventy Eighty Ninety'.split()
         
         if n == 0:
             return ''
         
         w = ""
 
         while n > 0:
             if n > 99:
                 digit = n//100
         
                 w += to19[digit-1] + ' ' + 'Hundred'
                 n = n % 100
                 
                 if n != 0:
                     w += ' '
                 
             else:
                 if n <= 19:
                     w +=  to19[n-1]
                     n = 0
                 else:
                     digit = n// 10
                     w += tens[digit-2] 
                     n = n % 10
                     
                     if n != 0:
                         w += ' '
                     
         return w
                             
         
     def numberToWords(self, num):
         """
         :type num: int
         :rtype: str
         """
         thousands = ['', ' Thousand ', ' Million ', ' Billion ']
         i = 0
         w = ""
         
         if num == 0:
             return 'Zero'
         
         while num > 0:
             digits = num % 1000
             if digits != 0:
                 w = self.parseHundred(digits) +  thousands[i] + w
             num = num//1000
             
             i += 1
             
         return w.strip()
         


class Solution:
     def numberToWords(self, num):
         return ' '.join(self.words(num)) or 'Zero'
         
         
     def words(self, n):
         print(n)
         to19 = ['One', 'Two', 'Three', 'Four', 'Five', 'Six', 'Seven', 'Eight', 'Nine', 'Ten', 'Eleven', 'Twelve', 'Thirteen', 'Fourteen', 'Fifteen', 'Sixteen', 'Seventeen', 'Eighteen', 'Nineteen']
         tens = ['Twenty', 'Thirty', 'Forty', 'Fifty', 'Sixty', 'Seventy', 'Eighty', 'Ninety',]
                         
         if n < 20:
             return to19[n - 1: n]
         if n < 100:
             return [tens[n//10 - 2]] + self.words(n%10)
         if n < 1000:
             return [to19[n//100 - 1]] + ['Hundred'] + self.words(n%100)
             
         for p, w in enumerate(('Thousand', 'Million', 'Billion'), 1):
             if n < 1000**(p + 1):
                 return self.words(n//1000**p)  + [w] + self.words(n%1000**p)
         
         """
         :type num: int
         :rtype: str
         """


class Solution:
     def numberToWords(self, num):
         """
         :type num: int
         :rtype: str
         """
         if num==0:
             return "Zero"
         res=""
         less20=["Zero","One","Two","Three","Four","Five","Six","Seven","Eight","Nine","Ten","Eleven","Twelve","Thirteen","Fourteen","Fifteen","Sixteen","Seventeen","Eighteen","Nineteen"]
         tens=["Zero","Ten","Twenty","Thirty","Forty","Fifty","Sixty","Seventy","Eighty","Ninety"]
         thousands=["","Thousand","Million","Billion"]
         for k in range(4):
             if num ==0:
                 break
             cur=""
             curNum=num%1000
             num//=1000
             print(("num",num))
             if curNum>=100:
                 x=curNum//100
                 curNum%=100
                 cur=less20[x]+" Hundred"
             if curNum>0:
                 if cur:
                     cur+=" "
                 if curNum<20:
                     cur+=less20[curNum]
                 else:
                     x=curNum//10
                     curNum%=10
                     cur+=tens[x]
                     if curNum!=0:
                         cur+=" "+less20[curNum]
             print("cur")
             if cur:
                 res=cur+((" "+thousands[k] if k else"")) +((" "+res if res else""))
         return res


class Solution:
     def __init__(self):
         self.twenties = ['', 'One', 'Two', 'Three', 'Four', 'Five', 'Six', 'Seven', 'Eight', 'Nine', 'Ten',
                       'Eleven', 'Twelve', 'Thirteen', 'Fourteen', 'Fifteen', 'Sixteen', 'Seventeen', 'Eighteen', 'Nineteen']
         self.tens = ['', 'Ten', 'Twenty', 'Thirty', 'Forty', 'Fifty', 'Sixty', 'Seventy', 'Eighty', 'Ninety']
         self.thousands = ['', 'Thousand', 'Million', 'Billion']
         
     def numberToWords(self, num):
         """
         :type num: int
         :rtype: str
         """
         if num == 0:
             return 'Zero'
         
         result = ''
         for i in range(len(self.thousands)):
             if num % 1000 != 0:
                 result = self.helper(num%1000) + self.thousands[i] + ' ' + result
             num //= 1000
     
         return result.strip()
     
     def helper(self, num):
         if num == 0:
             return ''
         elif num < 20:
             return self.twenties[num] + ' '
         elif num < 100:
             return self.tens[num//10] + ' ' + self.helper(num%10)
         else:
             return self.twenties[num//100] + ' Hundred ' + self.helper(num%100)


class Solution:
     def numberToWords(self, num):
         """
         :type num: int
         :rtype: str
         """
 
         # special case 0
         def translate(num):
             if num == 0: return ''
             less20 = [
                 '', 'One', 'Two', 'Three', 'Four', 'Five', 'Six', 'Seven', 'Eight', 'Nine'
                 , 'Ten', 'Eleven', 'Twelve', 'Thirteen', 'Fourteen', 'Fifteen', 'Sixteen', 'Seventeen'
                 , 'Eighteen', 'Nineteen'
             ]
 
             more20 = ['', '', 'Twenty', 'Thirty', 'Forty', 'Fifty', 'Sixty', 'Seventy', 'Eighty', 'Ninety']
 
             res = ''
             if num // 100:
                 res = less20[num // 100] + ' Hundred' + (' ' if num % 100 else '')
 
             num %= 100
             res += less20[num] if num < 20 else more20[num // 10] + (' ' + less20[num % 10] if num % 10 else '')
             return res
         
         if num == 0: return 'Zero'
 
         unit = ['', 'Thousand', 'Million', 'Billion']
         i = 0
         res = []
         while num > 0:
             t = translate(num % 1000)
             if t:
                 res += [unit[i], t]
             num //= 1000
             i += 1
 
         return (' '.join(res[::-1])).strip()

class Solution:
     
     digit = {
         0: '',
         1: 'One',
         2: 'Two',
         3: 'Three',
         4: 'Four',
         5: 'Five',
         6: 'Six',
         7: 'Seven',
         8: 'Eight',
         9: 'Nine'
         }
     
     teen = {
         10: 'Ten',
         11: 'Eleven',
         12: 'Twelve',
         13: 'Thirteen',
         14: 'Fourteen',
         15: 'Fifteen',
         16: 'Sixteen',
         17: 'Seventeen',
         18: 'Eighteen',
         19: 'Nineteen'
     }
     
     ten = {
         2: 'Twenty',
         3: 'Thirty',
         4: 'Forty',
         5: 'Fifty',
         6: 'Sixty',
         7: 'Seventy',
         8: 'Eighty',
         9: 'Ninety'
     }
     
     idx = {
         0: '',
         1: 'Thousand',
         2: 'Million',
         3: 'Billion',
         4: 'Trillion',
         5: 'Quadrillion'
     }
     def helper(self,num):
         result = ""
         while len(num) < 3:
             num = '0' + num   
         
         if num[0] is not '0':
             result = self.digit[int(num[0])] + ' Hundred'
         if num[1] is not '0':
             if num[1] == '1':
                 return result + " " + self.teen[int(num[1]+num[2])]
             else:
                 return result + " " + self.ten[int(num[1])] + " " + self.digit[int(num[2])]
         if num[2] is not '0':
             result = result + " " + self.digit[int(num[2])]
         return result
     
     def numberToWords(self, num):
         """
         :type num: int
         :rtype: str
         """
         if num == 0:
             return 'Zero'
         result = ""
         rev = str(num)[::-1]
         slices = [rev[i:i+3] for i in range(0,len(str(num)),3)]
         
         for idx, slice in enumerate((slices)):
             if slice == '000':
                 continue
             else:
                 result = self.helper(str(slice[::-1])) + " " + self.idx[idx] + " "+ result
         result = result.split(' ')
         result = [ x for x in result if x is not ""]   
         return ' '.join(result)
     
 


class Solution:
     def numberToWords(self, num):
         """
         :type num: int
         :rtype: str
         """
         num_lyst = ['', 'One', 'Two', 'Three', 'Four', 'Five', 'Six', 'Seven', 'Eight', 'Nine']
         tens_lyst = ['', '', 'Twenty', 'Thirty', 'Forty', 'Fifty', 'Sixty', 'Seventy', 'Eighty', 'Ninety']
         under20_lyst = ['Ten', 'Eleven', 'Twelve', 'Thirteen', 'Fourteen', 'Fifteen', 'Sixteen', 'Seventeen', 'Eighteen', 'Nineteen']
         large_scale = ['', 'Thousand', 'Million', 'Billion']
         
         def convert(num):
             out_str = ''
             hundred = num // 100
             ten_digit = num % 100
             if hundred:
                 out_str += num_lyst[hundred] + ' ' + 'Hundred '
             if ten_digit:
                 if ten_digit < 10:
                     out_str += num_lyst[ten_digit]
                 elif ten_digit < 20:
                     out_str += under20_lyst[ten_digit % 10]
                 else:
                     out_str += tens_lyst[ten_digit // 10] + ' ' + num_lyst[ten_digit % 10]
                     
             return out_str.strip()
         
         if not num:
             return 'Zero'
         
         
         res = num // 1000    # 商
         last3 = num % 1000     # 余数，后三位
         ans = ''
 
         while res or last3:
             if last3:
                 ans = convert(last3) + ' ' + large_scale.pop(0) + ' '+ ans
             else:
                 large_scale.pop(0)
             
             last3 = res % 1000
             res = res //1000
             
         return ans.strip()
                 
             
                 
                 
             
             


class Solution:
     def getEnglishThousand(self, n):
         if 1 <= n <= 9:
             return ['One', 'Two', 'Three', 'Four', 'Five', 'Six', 'Seven', 'Eight', 'Nine'][n-1]
         elif 10 <= n <= 19:
             return ['Ten', 'Eleven', 'Twelve', 'Thirteen', 'Fourteen', 'Fifteen', 'Sixteen', 'Seventeen', 'Eighteen', 'Nineteen'][n-10]
         elif 20 <= n <= 99:
             eng = ['Twenty', 'Thirty', 'Forty', 'Fifty', 'Sixty', 'Seventy', 'Eighty', 'Ninety'][(n//10)-2]
             if n % 10 > 0:
                 return eng + ' ' + self.getEnglishThousand(n % 10)
             else:
                 return eng
         else:
             hundred = self.getEnglishThousand(n // 100) + ' Hundred'
             if n % 100 > 0:
                 return hundred + ' ' + self.getEnglishThousand(n % 100)
             else:
                 return hundred
 
     def numberToWords(self, num):
         """
         :type num: int
         :rtype: str
         """
         if num == 0:
             return 'Zero'
         stack = ['Billion', 'Million', 'Thousand', None]
         english = []
         while num:
             quantifier = stack.pop()
             if num % 1000 > 0:
                 english.append(self.getEnglishThousand(num % 1000) + (' ' + quantifier if quantifier else ''))
             num //= 1000
         return ' '.join(reversed(english))

class Solution:
 
     quantity_unit = ['', 'Thousand', 'Million', 'Billion']
     digit_to_str = ['', ' One', ' Two', ' Three', ' Four', ' Five', ' Six', ' Seven', ' Eight', ' Nine']
 
     ten_to_str = {10: 'Ten', 11: 'Eleven', 12: 'Twelve', 13: 'Thirteen', 14: 'Fourteen', 15: 'Fifteen', 16: 'Sixteen',
                   17: 'Seventeen', 18: 'Eighteen', 19: 'Nineteen', 20: 'Twenty', 30: 'Thirty', 40: 'Forty', 50: 'Fifty',
                   60: 'Sixty', 70: 'Seventy', 80: 'Eighty', 90: 'Ninety', 0: ''}
 
     def read_three_digits(self, unit, ten, hundred, index):
 
         if ten == 1:
             str_of_num = ' ' + Solution.ten_to_str[ten * 10 + unit]
         else:
             str_of_num = (' ' + Solution.ten_to_str[ten * 10] + Solution.digit_to_str[unit]) if ten > 1 else Solution.digit_to_str[unit]
 
         str_of_num = (Solution.digit_to_str[hundred] + ' Hundred' if hundred > 0 else "") + str_of_num
         # print(str_of_num + str(index))
         return str_of_num[1:] + ' ' + Solution.quantity_unit[index] if str_of_num else str_of_num[1:]
 
     def numberToWords(self, num):
         """
         :type num: int
         :rtype: str
         """
         if num == 0:
             return 'Zero'
 
         str_of_num = ""
         index = 0
         while num > 0:
             part = num % 1000
             unit = part % 10
             ten = (part % 100) // 10
             hundred = part // 100
             str_of_num = self.read_three_digits(unit, ten, hundred, index) + ' ' + str_of_num.strip()
             num //= 1000
             index += 1
         return str_of_num.strip()