273. Integer to English Words
1. Description
Convert a non-negative integer num to its English words representation.
2. Example
Example 1
Input: num = 123
Output: “One Hundred Twenty Three”
Example 2
Input: num = 12345
Output: “Twelve Thousand Three Hundred Forty Five”
Example 3
Input: num = 1234567
Output: “One Million Two Hundred Thirty Four Thousand Five Hundred Sixty Seven”
3. Constraints
- 0 <= num <= 2$^{31}$ - 1
4. Solutions
Greedy
n = num
Time complexity: O(n)
Space complexity: O(1)
class Solution {
public:
string numberToWords(int num) {
if (num == 0) {
return "Zero";
}
string result;
int index = 0;
while (num > 0) {
int current = num % 1000;
if (current != 0) {
string part = convert_to_words(current);
if (!units[index].empty()) {
part += " " + units[index];
}
if (!result.empty()) {
part += " ";
}
result = part + result;
}
++index;
num /= 1000;
}
return result;
}
private:
const array<string, 10>
ones{"", "One", "Two", "Three", "Four", "Five", "Six", "Seven", "Eight", "Nine"};
const array<string, 10> teens{
"Ten",
"Eleven",
"Twelve",
"Thirteen",
"Fourteen",
"Fifteen",
"Sixteen",
"Seventeen",
"Eighteen",
"Nineteen"};
const array<string, 10>
tens{"", "", "Twenty", "Thirty", "Forty", "Fifty", "Sixty", "Seventy", "Eighty", "Ninety"};
const array<string, 4> units{"", "Thousand", "Million", "Billion"};
string convert_to_words(int num) {
string result;
if (num >= 100) {
result += ones[num / 100] + " Hundred";
num %= 100;
if (num > 0) {
result += " ";
}
}
if (num >= 20) {
result += tens[num / 10];
if (num % 10 > 0) {
result += " " + ones[num % 10];
}
} else if (num >= 10) {
result += teens[num - 10];
} else if (num > 0) {
result += ones[num];
}
return result;
}
};