/**
* Time complexity :
* Space complexity :
*/
class Solution {
private Map<Integer, String> map = new HashMap();
private final String EMPTY = " ";
public String numberToWords(int num) {
loadMap();
if(num <= 20) {
return map.get(num);
}
StringBuilder result = new StringBuilder();
if(num >= 1000000000) {
int extra = num / 1000000000;
result.append(convert(extra)).append(" Billion");
num %= 1000000000;
}
if(num >= 1000000) {
int extra = num / 1000000;
result.append(convert(extra)).append(" Million");
num %= 1000000;
}
if(num >= 1000) {
int extra = num / 1000;
result.append(convert(extra)).append(" Thousand");
num %= 1000;
}
if(num > 0) {
result.append(convert(num));
}
return result.toString().trim();
}
private String convert(int n) {
StringBuilder result = new StringBuilder();
if(n >= 100) {
int nHundreds = n / 100;
result.append(EMPTY).append(map.get(nHundreds)).append(" Hundred");
n %= 100;
}
if(n > 0) {
if(n <= 20) {
result.append(EMPTY).append(map.get(n));
n %= 100;
} else {
int nTens = n / 10;
result.append(EMPTY).append(map.get(nTens * 10));
n %= 10;
if(n > 0) {
result.append(EMPTY).append(map.get(n));
}
}
}
return result.toString();
}
private void loadMap() {
if(map.isEmpty()) {
map.put(0, "Zero");
map.put(1, "One");
map.put(2, "Two");
map.put(3, "Three");
map.put(4, "Four");
map.put(5, "Five");
map.put(6, "Six");
map.put(7, "Seven");
map.put(8, "Eight");
map.put(9, "Nine");
map.put(10, "Ten");
map.put(11, "Eleven");
map.put(12, "Twelve");
map.put(13, "Thirteen");
map.put(14, "Fourteen");
map.put(15, "Fifteen");
map.put(16, "Sixteen");
map.put(17, "Seventeen");
map.put(18, "Eighteen");
map.put(19, "Nineteen");
map.put(20, "Twenty");
map.put(30, "Thirty");
map.put(40, "Forty");
map.put(50, "Fifty");
map.put(60, "Sixty");
map.put(70, "Seventy");
map.put(80, "Eighty");
map.put(90, "Ninety");
}
}
}