Problem description:

Convert a non-negative integer to its english words representation. Given input is guaranteed to be less than 2^31 - 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”

Solution:

Question can ask in interview:

  1. What format is the integer? contain dots? floating number?
  2. Input type, integer/string
  3. Output type, should be string
  4. time/space complexity restriction

The hint from this question, Group the number by thousands (3 digits). Write a helper function that takes a number less than 1000 and convert just that chunk to words.

  1. use some example to demonstrate how to set up the array.
    1~19, all different words
    20~99, different words too
    100~999, can be constructed by previous two with "Hundred".
    greater than 1000, can use previous three with "Thousand", "Million", "Billion".

  2. After creating the dictionary, we can try to divide the question into smaller pieces. Since the result with num greater than 1000 are similar, we can use a helper function to construct strings less than 1000.

  3. Dealing with num greater than thousands. The pattern is to divide num with 1000 multiple times and counting how many 1000 we have divided.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class Solution:
    def numberToWords(self, num: int) -> str:
        self.lessThan20 = ["","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"]
        
        # zero
        # divide by 1000 many times, 
        # 105,004,000 -> first time //= 1000 would get module 4
        # second time would get 5
        if num == 0:
            return "Zero"
        
        res = ""
        for i in range(len(self.thousands)):
            if num % 1000 != 0: # need to add something to the module number
                res = self.helper(num%1000) + self.thousands[i] + " " + res
            num //= 1000
        return res.strip()
    def helper(self, num):
        if num == 0:
            return ""
        elif num < 20:
            return self.lessThan20[num] + " "
        elif num < 100:
            return self.tens[num//10] + " " + self.helper(num%10)
        else:
            return self.lessThan20[num//100] + " Hundred " + self.helper(num%100)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
class Solution {
public:
    vector<string> less_than_20= {"", "One", "Two", "Three", "Four", "Five", "Six", "Seven", "Eight", "Nine", "Ten", "Eleven", "Twelve", "Thirteen", "Fourteen", "Fifteen", "Sixteen", "Seventeen", "Eighteen", "Nineteen"};
    vector<string> tens= {"", "Ten", "Twenty", "Thirty", "Forty", "Fifty", "Sixty", "Seventy", "Eighty", "Ninety"};
    vector<string> thousands= {"", "Thousand", "Million", "Billion"};
    
    string numberToWords(int num) {
        if(num == 0) return "Zero";
        int i= 0;
        string res= "";
        
        while(num> 0){
            if(num%1000 != 0)
                res= helper(num%1000)+ thousands[i]+ " "+ res;
            num /= 1000;
            i++;
        }
        return res.substr(0, res.find_last_not_of(' ')+1);
    }
    
    string helper(int num){
        if(num == 0) return "";
        else if(num < 20)
            return less_than_20[num]+ " ";
        else if(num < 100)
            return tens[num/10]+ " "+ helper(num%10);
        else
            return less_than_20[num/100]+ " Hundred "+ helper(num%100);
    }
};

time complexity: $O(1)$, because the length of num is limited and the loop will be called constant number of times.

reference:
http://www.cnblogs.com/grandyang/p/4772780.html