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: Recursion
Time complexity: O(logn)
Space complexity: O(logn)
C++
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 |
// Author: Huahua constexpr char * kUnder20[] = {"One", "Two", "Three", "Four", "Five", "Six", "Seven", "Eight", "Nine","Ten", "Eleven", "Twelve", "Thirteen", "Fourteen", "Fifteen", "Sixteen", "Seventeen", "Eighteen", "Nineteen"}; constexpr char * kUnder100[] = {"Twenty", "Thirty", "Forty", "Fifty", "Sixty", "Seventy", "Eighty", "Ninety"}; constexpr char * kHTMB[] = {"Hundred", "Thousand", "Million", "Billion"}; constexpr long kP[] = {100, 1000, 1000*1000, 1000*1000*1000}; class Solution { public: string numberToWords(int n) { if (n == 0) return "Zero"; return convert(n).substr(1); } private: string convert(int n) { if (n == 0) return ""; if (n < 20) return string(" ") + kUnder20[n - 1]; // 1 - 19 if (n < 100) return string(" ") + kUnder100[n / 10 - 2] + convert(n % 10); // 20 ~ 99 for (int i = 3; i >= 0; --i) if (n >= kP[i]) return convert(n / kP[i]) + " " + kHTMB[i] + convert(n % kP[i]); return ""; } }; |