273. Integer to English Words
思路：感覺就是 edge case 很多的題目，使用分進合擊的方式每百位數 0~999 進行處理
但是一堆空格會導致需要一堆條件判斷
跑起來速度大家都差不多，但是記憶體用量意外得少
https://i.imgur.com/BJiQQDh.png
class Solution {
public:
string numberToWords(int num) {
string result = "";
int decimalPostFix = 0;
do {
string hundredsString =
hundredsToString(num % 1000, decimalPostFix);
if (hundredsString != "") {
if (result == "") {
result = hundredsString;
} else {
result = hundredsString + " " + result;
}
}
num /= 1000;
decimalPostFix++;
} while (num != 0);
if (result == "") {
return "Zero";
}
return result;
}
private:
const string HUNDRED = "Hundred";
const array<string, 4> decimalPointString = {
"",
" Thousand",
" Million",
" Billion",
};
const array<string, 20> zeroToNineteen = {
"Zero", "One", "Two", "Three", "Four",
"Five", "Six", "Seven", "Eight", "Nine",
"Ten", "Eleven", "Twelve", "Thirteen", "Fourteen",
"Fifteen", "Sixteen", "Seventeen", "Eighteen", "Nineteen",
};
const array<string, 10> tenString = {
"Zero", "Ten", "Twenty", "Thirty", "Forty",
"Fifty", "Sixty", "Seventy", "Eighty", "Ninety",
};
string hundredsToString(int hundreds, int decimalPostFixIndex) {
if (hundreds == 0) {
return "";
}
string result;
int hundred = hundreds / 100;
string hundredString = getHundredString(hundred);
int tens = hundreds % 100;
if (hundredString == "") {
return getTensString(tens) +
decimalPointString[decimalPostFixIndex];
} else {
string tensString = getTensString(tens);
if (tensString == "") {
return hundredString +
decimalPointString[decimalPostFixIndex];
}
return hundredString + " " + tensString +
decimalPointString[decimalPostFixIndex];
}
return result;
}
string getHundredString(int hundred) {
if (hundred == 0) {
return "";
}
return zeroToNineteen[hundred] + " " + HUNDRED;
}
string getTensString(int tens) {
if (tens == 0) {
return "";
}
if (1 <= tens && tens <= 19) {
return zeroToNineteen[tens];
}
int ten = tens / 10;
int singleDigit = tens % 10;
string singleDigitString = getSingleDigitString(singleDigit);
if (singleDigitString == "") {
return tenString[ten];
}
return tenString[ten] + " " + singleDigitString;
}
string getSingleDigitString(int singleDigit) {
if (singleDigit == 0) {
return "";
}
return zeroToNineteen[singleDigit];
}
};