Wednesday, September 2, 2015

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
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
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.
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'
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'

No comments:

Post a Comment