Description

Convert a non-negative integer to its english words representation. Given input is guaranteed to be less than 2³¹ - 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"

Solution

No algorithm, time O(n), space O(n)

麻烦题，corner case比较多，注意几点：

• 3位3位处理，添加单位；
• 100以内的数字，20以下有专门的单次，20以上需要组合；
• 对于100000这种，如果某个区间为0，直接跳过这个区间。

class Solution {
    private static final String[] UNITS = {"", " Thousand", " Million", " Billion"};
    private static final String[] SINGLES = {"", "One", "Two", "Three", "Four"
            , "Five", "Six", "Seven", "Eight", "Nine"
            , "Ten", "Eleven", "Twelve", "Thirteen", "Fourteen"
            , "Fifteen", "Sixteen", "Seventeen", "Eighteen", "Nineteen"};
    private static final String[] TENS = {"", "", "Twenty", "Thirty", "Forty"
            , "Fifty", "Sixty", "Seventy", "Eighty", "Ninety"};
    
    public String numberToWords(int num) {
        if (num == 0) {
            return "Zero";
        }
        
        StringBuilder res = new StringBuilder();
        
        for (int i = 0; i < 5 && num > 0; ++i) {
            int val = num % 1000;
            if (val == 0) { // jump to next part directly if current part is 0
                num /= 1000;
                continue;
            }
            
            String groupWords = getGroupWords(val, UNITS[i]);
            res.insert(0, res.length() > 0 ? " " : "");
            res.insert(0, groupWords);
            num /= 1000;
        }
        
        return res.toString();
    }
    
    private String getGroupWords(int val, String unit) {
        StringBuilder sb = new StringBuilder();
            
        if (val >= 100) {
            sb.append(SINGLES[val / 100]).append(" Hundred");
            val %= 100;
        }
        
        if (val >= 20) {
            sb.append(sb.length() > 0 ? " " : "").append(TENS[val / 10]);
            val %= 10;
        }
        
        if (val >= 1) {
            sb.append(sb.length() > 0 ? " " : "").append(SINGLES[val]);
        }
        
        sb.append(unit);
        return sb.toString();
    }
}