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"

class Solution {
    Map<Integer, String> map = new HashMap<Integer, String>() 
    {{
        put(0, "Zero");
        put(1, "One");
        put(2, "Two");
        put(3, "Three");
        put(4, "Four");
        put(5, "Five");
        put(6, "Six");
        put(7, "Seven");
        put(8, "Eight");
        put(9, "Nine");
        put(10, "Ten");
        put(11, "Eleven");
        put(12, "Twelve");
        put(13, "Thirteen");
        put(14, "Fourteen");
        put(15, "Fifteen");
        put(16, "Sixteen");
        put(17, "Seventeen");
        put(18, "Eighteen");
        put(19, "Nineteen");
        put(20, "Twenty");
        put(30, "Thirty");
        put(40, "Forty");
        put(50, "Fifty");
        put(60, "Sixty");
        put(70, "Seventy");
        put(80, "Eighty");
        put(90, "Ninety");
        put(100, "Hundred");
        put(1000, "Thousand");
        put(1000000, "Million");
        put(1000000000, "Billion");
    }};

    public String numberToWords(int num) {
        if(num == 0) return map.get(0);
        if( num < 0) return "Negative " + toWords(Math.abs(num));

        return toWords(num);
    }

    public String toWords(int num) {
        if(num >= 1000000000) 
            return (toWords(num / 1000000000) + " " + map.get(1000000000) + " " + toWords(num % 1000000000)).trim();
        else if(num >= 1000000) 
            return (toWords(num / 1000000) + " " + map.get(1000000) + " " + toWords(num % 1000000)).trim();
        else if(num >= 1000) 
            return (toWords(num / 1000) + " " + map.get(1000) + " " + toWords(num % 1000)).trim();
        else if(num >= 100) 
            return (toWords(num / 100) + " " + map.get(100) + " " + toWords(num % 100)).trim();
        else if(num >= 20) 
            return (map.get((num/10) * 10) + " " + toWords(num % 10)).trim();
        else if(num > 0) 
            return map.get(num);

        return "";
    }

}