Problem:
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"
Solution:
The problem can be approached by breaking down the input into 3 digits groups, then translate each 3 digits group to string. It is not quite tedious, we must handle lots of edge conditions and implementation details in time constraint.
/*
1. break down to 3 digit groups.
0-2 no postfix
3-5 postfix Thousand
6-8 post fix Million
9- post fix Billion
...
2. handle 3 digits
digit at hundreds, pass to handle 1 digit
if digit at ten is not 1,
0 - ""
2 - Twenty
3 - Thirty
...
9 - Ninety
+ handle 1 digit for digit at lsb
if digit at ten is 1
10 - Ten
11 - Eleven
12 - Twelve
13 - Thirteen
14 - Fourteen
15 - Fifteen
...
19 - Nineteen
3. handle lest significant bit (lsb) digit
1 - One
2 - Two
...
9 - Nine
0 - ""
130
1000,000
*/
import java.util.*;
class Solution {
private String oneDigit(int i) {
switch(i) {
case 1: return "One";
case 2: return "Two";
case 3: return "Three";
case 4: return "Four";
case 5: return "Five";
case 6: return "Six";
case 7: return "Seven";
case 8: return "Eight";
case 9: return "Nine";
default: return "";
}
}
private String tenToNineTeen(int i) {
switch(i) {
case 10: return "Ten";
case 11: return "Eleven";
case 12: return "Twelve";
case 13: return "Thirteen";
case 14: return "Fourteen";
case 15: return "Fifteen";
case 16: return "Sixteen";
case 17: return "Seventeen";
case 18: return "Eighteen";
case 19: return "Nineteen";
default: return "";
}
}
private String tensTranslate(int i) {
switch(i) {
case 2: return "Twenty";
case 3: return "Thirty";
case 4: return "Forty";
case 5: return "Fifty";
case 6: return "Sixty";
case 7: return "Seventy";
case 8: return "Eighty";
case 9: return "Ninety";
default: return "";
}
}
public String numberToWords(int num) {
if(num == 0)
return "Zero";
int lsb = 0;
int acc = 0;
int group = 0;
int a = 0, b = 0, c = 0;
StringBuffer sb = new StringBuffer();
while(num > 0) {
for(int i = 0; i <= 2; i++) {
lsb = num - (num/10) * 10;
if(i == 0) {
a = lsb;
} else if(i == 1) {
b = lsb;
} else if(i == 2) {
c = lsb;
}
num = (num - lsb)/10;
}
String str = handleThreeDigits(a, b, c);
if(str.length() == 0) {
group++;
continue;
}
sb.insert(0, sb.length() > 0 ? " ": "");
if(group == 0) {
sb.insert(0, str);
} else if(group == 1) {
sb.insert(0, " Thousand");
sb.insert(0, str);
} else if(group == 2) {
sb.insert(0, " Million");
sb.insert(0, str);
} else if(group == 3) {
sb.insert(0, " Billion");
sb.insert(0, str);
}
group++;
}
return sb.toString();
}
private String handleThreeDigits(int lsb, int tens, int hundreds) {
if(hundreds == 0) {
return handleTens(tens, lsb);
} else if(tens == 0 && lsb == 0) {
return handleHundreds(hundreds);
} else {
return handleHundreds(hundreds) + " " + handleTens(tens, lsb);
}
}
private String handleTens(int tens, int lsb) {
if(tens == 0) {
return handleOneDigit(lsb);
} else if(tens == 1) {
return tenToNineTeen(10 + lsb);
} else {
if(lsb == 0) {
return tensTranslate(tens);
}
return tensTranslate(tens) + " " + handleOneDigit(lsb);
}
}
private String handleHundreds(int d) {
if(d == 0) return "";
return handleOneDigit(d) + " Hundred";
}
private String handleOneDigit(Integer d) {
return oneDigit(d);
}
}
Time complexity O(N) for processing each digit in the number, space complexity O(N) for the store each digit corresponded string in a tmp string or string buffer.
