## 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;

}
};
``````