273. Integer to English Words

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"

Thoughts: 1. Only limited cases, enumerate all of them out:

Hundred: 100

Thousand: 1,000

Million: 1,000,000

Billion: 1,000,000,000

• all the tenth + 1 - 9

• Build the string by recursively first processing the dividend, then reminder.

• Only write "zero" when input is just '0', else ''

Code：

class Solution {
    public String numberToWords(int num) {
         // base case
        if(num == 0) return "Zero";
        String[] words = {"", "One", "Two", "Three", "Four", "Five", "Six", "Seven", "Eight", "Nine",
        "Ten", "Eleven", "Twelve", "Thirteen", "Fourteen", "Fifteen", "Sixteen", "Seventeen", "Eighteen", "Nineteen",
        "Twenty", "Thirty", "Forty", "Fifty", "Sixty", "Seventy", "Eighty", "Ninety"};
        return process(words, num);
    }

    private String process(String [] words, int num){
        String ans = "";
        if (num >= 1000000000) { //1,000,000,000 
            ans += process(words, num / 1000000000) + " " + "Billion" + " " + process(words,num%1000000000);
        }
        else if (num >= 1000000) { //1,000,000
            ans += process(words, num / 1000000) + " " + "Million" + " " + process(words,num%1000000);
        }
        else if (num >= 1000) { //1,000
            ans += process(words, num / 1000) + " " + "Thousand" + " " + process(words,num%1000);
        }
        else if (num >= 100) { //100
            ans += process(words, num / 100) + " " + "Hundred" + " " + process(words,num%100);
        }
        else if (num >= 20){
            ans += words[(num - 20)/10 + 20] + " " + process(words, num %10);
        }
        else{
            ans += words[num];
        }
            return ans.trim(); // trim here to get rid of extra whitespace due to process 0
    }
}

Code: C++ with trim() implementation

class Solution {
public:
    string numberToWords(int num) {
        // base case
        if(num == 0) return "Zero";
        vector<string> words = {"", "One", "Two", "Three", "Four", "Five", "Six", "Seven", "Eight", "Nine",
        "Ten", "Eleven", "Twelve", "Thirteen", "Fourteen", "Fifteen", "Sixteen", "Seventeen", "Eighteen", "Nineteen", "Twenty", "Thirty", "Forty", "Fifty", "Sixty", "Seventy", "Eighty", "Ninety"};
        return process(words, num);
    }
private:
    string process(vector<string> words, int num){
        string ans = "";
        if (num >= 1000000000) { //1,000,000,000 
            ans += process(words, num / 1000000000) + " " + "Billion" + " " + process(words,num%1000000000);
        }
        else if (num >= 1000000) { //1,000,000
            ans += process(words, num / 1000000) + " " + "Million" + " " +  process(words,num%1000000);
        }
        else if (num >= 1000) { //1,000
            ans += process(words, num / 1000) + " " + "Thousand" + " " + process(words,num%1000);
        }
        else if (num >= 100) { //100
            ans += process(words, num / 100) + " " + "Hundred" + " " + process(words,num%100);
        }
        else if (num >= 20){
            ans += words[(num - 20)/ 10 + 20] + " " + process(words, num %10);
        }
        else {
            ans += words[num];
        }

            return trim(ans);
    }

    string trim(string str){
        // cout<< str<<endl;
        // if (str == " " ) return ""; 
        int startpos = 0, endpos = str.size() -1;
        while(startpos < str.size()){
            if(str[startpos] == ' ' ) { startpos ++;}
            else break;
        }

       while(endpos > 0){
            if(str[endpos] == ' ') endpos --;
            else break;
        } 
        if(endpos >= startpos){
            str = str.substr(startpos, endpos - startpos + 1);
        }
        return str;

    }
};