Integer to English Words [LeetCode]

Problem Description

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

For example,

123 -> "One Hundred Twenty Three"
12345 -> "Twelve Thousand Three Hundred Forty Five"
1234567 -> "One Million Two Hundred Thirty Four Thousand Five Hundred Sixty Seven"

Solution
To solve it, we divide the input number into chunks so that each has 3 digits.
One note about this LeetCode problem is that some edge cases such as "101" is considered as "One Hundred One" instead of "One Hundred And One". So this should not be correct in real life application!

I. Java Solution

view plainprint?

1. public class Solution {  
2.       
3.     String[] map1 = new String [] {"", " One", " Two", " Three", " Four", " Five",   
4.             " Six", " Seven", " Eight", " Nine", " Ten", " Eleven", " Twelve",   
5.             " Thirteen", " Fourteen", " Fifteen", " Sixteen", " Seventeen",   
6.             " Eighteen", " Nineteen" };  
7.               
8.     String[] map2 = new String[] {"", "", " Twenty", " Thirty", " Forty", " Fifty", " Sixty",   
9.         " Seventy", " Eighty", " Ninety" };  
10.           
11.     String[] map3 = new String[] {"", " Thousand", " Million", " Billion" };  
12.     final String HUNDRED = " Hundred";  
13.       
14.     public String threeDigitToWords(int num){  
15.         String result = "";  
16.         if (num > 99){  
17.             result = map1[num / 100] + HUNDRED;  
18.         }  
19.         num %= 100;  
20.         if(num < 20){  
21.             result +=  map1[num];  
22.         }else {  
23.             result += map2[num/10] + map1[num%10];  
24.         }  
25.         return result;  
26.     }  
27.       
28.     public String numberToWords(int num) {  
29.         if (num == 0) return "Zero";  
30.         String result = "";  
31.           
32.         int i = 0; //check if it is thousand, million, billion  
33.         while(num != 0){  
34.             if(num % 1000 != 0)  
35.                 result = threeDigitToWords(num % 1000) + map3[i] + result;  
36.             i++;  
37.             num /= 1000;  
38.         }  
39.         return result.trim();  
40.     }  
41. }  

public class Solution {
    
    String[] map1 = new String [] {"", " One", " Two", " Three", " Four", " Five", 
            " Six", " Seven", " Eight", " Nine", " Ten", " Eleven", " Twelve", 
            " Thirteen", " Fourteen", " Fifteen", " Sixteen", " Seventeen", 
            " Eighteen", " Nineteen" };
            
    String[] map2 = new String[] {"", "", " Twenty", " Thirty", " Forty", " Fifty", " Sixty", 
        " Seventy", " Eighty", " Ninety" };
        
    String[] map3 = new String[] {"", " Thousand", " Million", " Billion" };
    final String HUNDRED = " Hundred";
    
    public String threeDigitToWords(int num){
        String result = "";
        if (num > 99){
            result = map1[num / 100] + HUNDRED;
        }
        num %= 100;
        if(num < 20){
            result +=  map1[num];
        }else {
            result += map2[num/10] + map1[num%10];
        }
        return result;
    }
    
    public String numberToWords(int num) {
        if (num == 0) return "Zero";
        String result = "";
        
        int i = 0; //check if it is thousand, million, billion
        while(num != 0){
            if(num % 1000 != 0)
                result = threeDigitToWords(num % 1000) + map3[i] + result;
            i++;
            num /= 1000;
        }
        return result.trim();
    }
}

II. Python Solution

view plainprint?

1. class Solution(object):  
2.     def __init__(self):  
3.         self.map1 = ["", " One", " Two", " Three", " Four", " Five",   
4.             " Six", " Seven", " Eight", " Nine", " Ten", " Eleven", " Twelve",   
5.             " Thirteen", " Fourteen", " Fifteen", " Sixteen", " Seventeen",   
6.             " Eighteen", " Nineteen" ]  
7.               
8.         self.map2 = ["", "", " Twenty", " Thirty", " Forty", " Fifty", " Sixty",   
9.             " Seventy", " Eighty", " Ninety" ]  
10.               
11.         self.map3 = ["", " Thousand", " Million", " Billion"]  
12.         self.HUNDRED = " Hundred"  
13.           
14.     def threeDigitToWords(self, num):  
15.         result = ""  
16.         if num > 99 :   
17.             result = self.map1[num / 100] + self.HUNDRED  
18.   
19.         num %= 100  
20.         if num < 20:  
21.             result +=  self.map1[num]  
22.         else:  
23.             result += self.map2[num/10] + self.map1[num%10]  
24.           
25.         return result  
26.       
27.     def numberToWords(self, num):  
28.         """ 
29.         :type num: int 
30.         :rtype: str 
31.         """  
32.         if num == 0: return "Zero"  
33.         result = ""  
34.           
35.         i = 0 #check if it is thousand, million, billion  
36.         while num != 0:  
37.             if num % 1000 != 0:  
38.                 result = self.threeDigitToWords(num % 1000) + self.map3[i] + result  
39.             i+=1  
40.             num /= 1000  
41.           
42.         return result[1:];  

class Solution(object):
    def __init__(self):
        self.map1 = ["", " One", " Two", " Three", " Four", " Five", 
            " Six", " Seven", " Eight", " Nine", " Ten", " Eleven", " Twelve", 
            " Thirteen", " Fourteen", " Fifteen", " Sixteen", " Seventeen", 
            " Eighteen", " Nineteen" ]
            
        self.map2 = ["", "", " Twenty", " Thirty", " Forty", " Fifty", " Sixty", 
            " Seventy", " Eighty", " Ninety" ]
            
        self.map3 = ["", " Thousand", " Million", " Billion"]
        self.HUNDRED = " Hundred"
        
    def threeDigitToWords(self, num):
        result = ""
        if num > 99 : 
            result = self.map1[num / 100] + self.HUNDRED

        num %= 100
        if num < 20:
            result +=  self.map1[num]
        else:
            result += self.map2[num/10] + self.map1[num%10]
        
        return result
    
    def numberToWords(self, num):
        """
        :type num: int
        :rtype: str
        """
        if num == 0: return "Zero"
        result = ""
        
        i = 0 #check if it is thousand, million, billion
        while num != 0:
            if num % 1000 != 0:
                result = self.threeDigitToWords(num % 1000) + self.map3[i] + result
            i+=1
            num /= 1000
        
        return result[1:];

Appendix B: Pythonic Solution
Below is the short pythonic code.

view plainprint?

1. class Solution(object):  
2.     def numberToWords(self, num):  
3.         """ 
4.         :type num: int 
5.         :rtype: str 
6.         """  
7.         def make_lists(s): return [[]] + [[i] for i in s.split()]  
8.           
9.         under20 =  make_lists('One Two Three Four Five Six Seven Eight Nine Ten Eleven Twelve ' \  
10.                'Thirteen Fourteen Fifteen Sixteen Seventeen Eighteen Nineteen')  
11.         tens = [[]] + make_lists('Twenty Thirty Forty Fifty Sixty Seventy Eighty Ninety')  
12.         thousands =  make_lists("Thousand Million Billion")  
13.           
14.         def threeDigitToWords(n):  
15.             return (under20[n/100] + ['Hundred'] if n>99 else []) + tens[n%100/10] + (under20[n%100] if n%100 < 20 else under20[n%100%10])  
16.               
17.         def toWords(n,i):  
18.             return (toWords(n/1000,i+1) if n else []) + threeDigitToWords(n%1000) + (thousands[i] if n%1000 else [])    
19.           
20.         return ' '.join(toWords(num,0)) or 'Zero'  

class Solution(object):
    def numberToWords(self, num):
        """
        :type num: int
        :rtype: str
        """
        def make_lists(s): return [[]] + [[i] for i in s.split()]
        
        under20 =  make_lists('One Two Three Four Five Six Seven Eight Nine Ten Eleven Twelve ' \
               'Thirteen Fourteen Fifteen Sixteen Seventeen Eighteen Nineteen')
        tens = [[]] + make_lists('Twenty Thirty Forty Fifty Sixty Seventy Eighty Ninety')
        thousands =  make_lists("Thousand Million Billion")
        
        def threeDigitToWords(n):
            return (under20[n/100] + ['Hundred'] if n>99 else []) + tens[n%100/10] + (under20[n%100] if n%100 < 20 else under20[n%100%10])
            
        def toWords(n,i):
            return (toWords(n/1000,i+1) if n else []) + threeDigitToWords(n%1000) + (thousands[i] if n%1000 else [])  
        
        return ' '.join(toWords(num,0)) or 'Zero'

view plainprint?

1. class Solution(object):  
2.     def numberToWords(self, num):  
3.         """ 
4.         :type num: int 
5.         :rtype: str 
6.         Credited: LeetCode 
7.         """  
8.         under20 = 'One Two Three Four Five Six Seven Eight Nine Ten Eleven Twelve ' \  
9.                'Thirteen Fourteen Fifteen Sixteen Seventeen Eighteen Nineteen'.split()  
10.         tens = 'Twenty Thirty Forty Fifty Sixty Seventy Eighty Ninety'.split()  
11.         def find_words(n):  
12.             if n < 20:  
13.                 return under20[n-1:n]  
14.             if n < 100:  
15.                 return [tens[n/10-2]] + find_words(n%10)  
16.             if n < 1000:  
17.                 return [under20[n/100-1]] + ['Hundred'] + find_words(n%100)  
18.             for p, w in enumerate(('Thousand', 'Million', 'Billion'), 1):  
19.                 if n < 1000**(p+1):  
20.                     return find_words(n/1000**p) + [w] + find_words(n%1000**p)  
21.         return ' '.join(find_words(num)) or 'Zero'  

class Solution(object):
    def numberToWords(self, num):
        """
        :type num: int
        :rtype: str
        Credited: LeetCode
        """
        under20 = '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()
        def find_words(n):
            if n < 20:
                return under20[n-1:n]
            if n < 100:
                return [tens[n/10-2]] + find_words(n%10)
            if n < 1000:
                return [under20[n/100-1]] + ['Hundred'] + find_words(n%100)
            for p, w in enumerate(('Thousand', 'Million', 'Billion'), 1):
                if n < 1000**(p+1):
                    return find_words(n/1000**p) + [w] + find_words(n%1000**p)
        return ' '.join(find_words(num)) or 'Zero'