273. Integer to English Words

问题

Convert a non-negative integer to its english words representation. Given input is guaranteed to be less than 231 - 1.

例子

123 -> "One Hundred Twenty Three"
12345 -> "Twelve Thousand Three Hundred Forty Five"
1234567 -> "One Million Two Hundred Thirty Four Thousand Five Hundred Sixty Seven"

分析

int的最大值为2147483647，所以一个int最多可以被表示成X Billion X Million X Thousand X，其中X部分又可以被表示成Y Hundred Z. 所以解决问题的关键是把数字切割成若干部分，每一部分都可以被简单地表示出来。

要点

• 映射表
• 分类讨论

时间复杂度

O(n), n为数字位数

空间复杂度

O(1)

代码

class Solution {
public:
    string numberToWords(int num) {
        if (num == 0) return string("Zero");
        string res;
        for (int i = 3; i >= 0; i--) {
            int div = pow(1000, i);
            int n = (num - num % div) / div;
            if (n != 0) {
                res += toStr000(n) + " ";
                if (num >= 1000)
                    res += str00[i] + " ";
            }
            num %= div;
        }
        res.pop_back();
        return res;
    }

private:
    string toStr000(int num) {
        string res;
        int n = num / 100;
        if (n != 0)
            res += str1[n] + " " + str00[0] + " ";
        num %= 100;
        n = num / 10;
        int d = num % 10;
        if (n != 0) {
            if (n == 1) res += str1x[d] + " ";
            else res += strx0[n - 2] + " ";
        }
        if (n != 1 && d != 0)
            res += str1[d] + " ";
        res.pop_back();
        return res;
    }

    vector<string> str1{ "Zero", "One", "Two", "Three", "Four", "Five", "Six", "Seven", "Eight", "Nine" };
    vector<string> str1x{ "Ten", "Eleven", "Twelve", "Thirteen", "Fourteen", "Fifteen", "Sixteen", "Seventeen", "Eighteen", "Nineteen" };
    vector<string> strx0{ "Twenty", "Thirty", "Forty", "Fifty", "Sixty", "Seventy", "Eighty", "Ninety" };
    vector<string> str00{ "Hundred", "Thousand", "Million", "Billion" };
};

more concise

class Solution {
 public:
    string digits[20] = {"Zero", "One", "Two", "Three", "Four", "Five", "Six", "Seven", "Eight", "Nine", "Ten", "Eleven", "Twelve", "Thirteen", "Fourteen", "Fifteen", "Sixteen", "Seventeen", "Eighteen", "Nineteen"};
    string tens[10] = {"Zero", "Ten", "Twenty", "Thirty", "Forty", "Fifty", "Sixty", "Seventy", "Eighty", "Ninety"};

    string int2string(int n) {
        if (n >= 1000000000) {
            return int2string(n / 1000000000) + " Billion" + int2string(n % 1000000000);
        } else if (n >= 1000000) {
            return int2string(n / 1000000) + " Million" + int2string(n % 1000000);
        } else if (n >= 1000) {
            return int2string(n / 1000) + " Thousand" + int2string(n % 1000);
        } else if (n >= 100) {
            return int2string(n / 100) + " Hundred" + int2string(n % 100);
        } else if (n >= 20) {
            return  " " + tens[n / 10] + int2string(n % 10);
        } else if (n >= 1) {
            return " " + digits[n];
        } else {
            return "";
        }
    }

    string numberToWords(int num) {
        if (num == 0) {
            return "Zero";
        } else {
            string ret = int2string(num);
            return std::move(ret.begin()+1, ret.end(), std::back_inserter(result));
        }
    }
};