Convert a non-negative integer to its english words representation. Given input is guaranteed to be less than 231 - 1.
For example,
123 -> "One Hundred Twenty Three"
12345 -> "Twelve Thousand Three Hundred Forty Five"
1234567 -> "One Million Two Hundred Thirty Four Thousand Five Hundred Sixty Seven"
英语中都是每三位一切,如23,000。因此从个位开始往上, 每次/1000进行后对num%1000进行dfs后和对应的THOUSANDS写法拼接。DFS内部判断num是否等于0,小于20, 100或其它, 把高位先摘出来, 再递归处理低位, 低位可以通过取mod直接得到。
/*
* @lc app=leetcode id=273 lang=cpp
*
* [273] Integer to English Words
*/
// @lc code=start
class Solution
{
public:
const vector<string> LESS_THAN_20{"", "One", "Two", "Three", "Four", "Five", "Six", "Seven",
"Eight", "Nine", "Ten", "Eleven", "Twelve", "Thirteen",
"Fourteen", "Fifteen", "Sixteen", "Seventeen", "Eighteen", "Nineteen"};
const vector<string> TENS{"", "", "Twenty", "Thirty", "Forty", "Fifty", "Sixty", "Seventy", "Eighty", "Ninety"};
const vector<string> THOUSANDS{"", "Thousand", "Million", "Billion"};
string dfs(const int num)
{
if (num == 0)
return "";
else if (num < 20)
return LESS_THAN_20[num] + " ";
else if (num < 100)
return TENS[num / 10] + " " + dfs(num % 10);
else
return LESS_THAN_20[num / 100] + " Hundred " + dfs(num % 100);
}
string numberToWords(int num)
{
if (num == 0)
return "Zero";
string res;
for (int i = 0; num > 0; num /= 1000, ++i)
{
if (num % 1000 != 0)
{
res = dfs(num % 1000) + THOUSANDS[i] + " " + res;
}
}
const auto trim = [](string &s) {
while (s.compare(0, 1, " ") == 0)
s.erase(s.begin());
while (s.size() > 0 && s.compare(s.size() - 1, 1, " ") == 0)
s.erase(s.end() - 1);
};
trim(res);
return res;
}
};
// @lc code=end
class Solution {
private final String[] LESS_THAN_20 = {"", "One", "Two", "Three", "Four", "Five", "Six", "Seven",
"Eight", "Nine", "Ten", "Eleven", "Twelve", "Thirteen",
"Fourteen", "Fifteen", "Sixteen", "Seventeen", "Eighteen","Nineteen"};
private final String[] TENS = {"", "", "Twenty", "Thirty", "Forty", "Fifty", "Sixty", "Seventy", "Eighty", "Ninety"};
private final String[] THOUSANDS = {"", "Thousand", "Million", "Billion"};
private String helper(int num) {
if (num == 0) {
return "";
} else if (num < 20) {
return LESS_THAN_20[num] + " ";
} else if (num < 100) {
return TENS[num / 10] + " " + helper(num % 10);
} else {
return LESS_THAN_20[num / 100] + " Hundred " + helper(num % 100);
}
}
public String numberToWords(int num) {
if (num == 0) {
return "Zero";
}
String res = "";
int i = 0;
while (num > 0) {
if (num % 1000 != 0) {
res = helper(num % 1000) + THOUSANDS[i] + " " + res;
}
num /= 1000;
i++;
}
return res.trim();
}
}
时间复杂度O(N), N为位数.