Sunday, August 30, 2015

LeetCode [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.
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"
 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
28
29
30
31
32
33
34
35
36
37
class Solution {
    vector<string> lessThan20, tens, thousands;
public:
    string numberToWords(int num) {
        if(num==0) return "Zero";
        lessThan20 = vector<string>{"", "One", "Two", "Three", "Four", "Five", "Six", "Seven", "Eight", "Nine", "Ten", "Eleven", "Twelve", "Thirteen", "Fourteen", "Fifteen", "Sixteen", "Seventeen", "Eighteen", "Nineteen"};
        tens = vector<string>{"", "Ten", "Twenty", "Thirty", "Forty", "Fifty", "Sixty", "Seventy", "Eighty", "Ninety"};
        string ret = helper(num);
        string s;
        for(int i=0; i<ret.size(); ++i)
        {
            if((i>0 && ret[i]==' ' && ret[i-1]==' ') || (i==ret.size()-1 && ret[i]==' ')) continue;
            else s += ret[i];
        }
        return s;
    }

    string helper(int num)
    {
        if(num < 20) return lessThan20[num];
        else if(num<100){
            return tens[num/10] + " " + helper(num%10);
        }else if(num<1000)
        {
            return lessThan20[num/100] + " " + "Hundred" + " " + helper(num%100);
        }else if(num<1000000)
        {
            return helper(num/1000) + " " + "Thousand" + " " + helper(num%1000);
        }else if(num<1000000000)
        {
            return helper(num/1000000) + " " + "Million" + " " + helper(num%1000000);
        }else
        {
            return helper(num/1000000000) + " " + "Billion" + " " + helper(num%1000000000);
        }
    }
};

 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
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
class Solution {
    Map<Integer, String> map = new HashMap<>();
    public String numberToWords(int num) {
        map.put(0, "Zero");
        map.put(1, "One");
        map.put(2, "Two");
        map.put(3, "Three");
        map.put(4, "Four");
        map.put(5, "Five");
        map.put(6, "Six");
        map.put(7, "Seven");
        map.put(8, "Eight");
        map.put(9, "Nine");
        map.put(10, "Ten");
        map.put(11, "Eleven");
        map.put(12, "Twelve");
        map.put(13, "Thirteen");
        map.put(14, "Fourteen");
        map.put(15, "Fifteen");
        map.put(16, "Sixteen");
        map.put(17, "Seventeen");
        map.put(18, "Eighteen");
        map.put(19, "Nineteen");
        map.put(20, "Twenty");
        map.put(30, "Thirty");
        map.put(40, "Forty");
        map.put(50, "Fifty");
        map.put(60, "Sixty");
        map.put(70, "Seventy");
        map.put(80, "Eighty");
        map.put(90, "Ninety");
        map.put(100, "Hundred");
        map.put(1000, "Thousand");
        map.put(1000000, "Million");
        map.put(1000000000, "Billion");

        return helper(num);
    }

    String toString(int gra, int num){
        int cnt = num/gra;
        String s = helper(cnt) + " " + map.get(gra) ;
        int r = num%gra;
        if(r>0) s += " " + helper(r);
        return s;
    }

    String helper(int num){
        String s = "";
        if(num<=20) return map.get(num);
        else if(num<100){//(20, 100)
            int r = num%10;
            s = map.get(num-r);
            if(r>0) s += " " + helper(r);
            return s;
        }else if(num<1000){//[10 , 1000)
            s = toString(100, num);
        }else if(num<1000000){//[1000, 1000000)
            s = toString(1000, num);
        }else if(num<1000000000){//[1000000, 1000000000)
            s = toString(1000000, num);
        }else{//[1000000000, 
            s = toString(1000000000, num);
        }
        return s;
    }
}

No comments:

Post a Comment