Short clean Java solution


  • 112
    I
    public class Solution {
        private final String[] belowTen = new String[] {"", "One", "Two", "Three", "Four", "Five", "Six", "Seven", "Eight", "Nine"};
        private final String[] belowTwenty = new String[] {"Ten", "Eleven", "Twelve", "Thirteen", "Fourteen", "Fifteen", "Sixteen", "Seventeen", "Eighteen", "Nineteen"};
        private final String[] belowHundred = new String[] {"", "Ten", "Twenty", "Thirty", "Forty", "Fifty", "Sixty", "Seventy", "Eighty", "Ninety"};
        
        public String numberToWords(int num) {
            if (num == 0) return "Zero";
            return helper(num); 
        }
        
        private String helper(int num) {
            String result = new String();
            if (num < 10) result = belowTen[num];
            else if (num < 20) result = belowTwenty[num -10];
            else if (num < 100) result = belowHundred[num/10] + " " + helper(num % 10);
            else if (num < 1000) result = helper(num/100) + " Hundred " +  helper(num % 100);
            else if (num < 1000000) result = helper(num/1000) + " Thousand " +  helper(num % 1000);
            else if (num < 1000000000) result = helper(num/1000000) + " Million " +  helper(num % 1000000);
            else result = helper(num/1000000000) + " Billion " + helper(num % 1000000000);
            return result.trim();
        }
    }

  • 15
    H

    服了。。。。。。。。。。。。。太厉害。。。。。。。。。。。。。。。。


  • 12
    N

    Wonderful solution for this question. I am really hate this kind of question.


  • 6

    +1 Dislike this kind of question. Too many details to concern about... But really happy to find a wonderful and concise solution finally. Thanks for sharing!


  • 0
    A

    What is the run time complexity for this solution?


  • 2
    I

    @acheiver, the run time complexity is O(1).
    In the worst case scenario, when a number is greater than one billion, for example, the function helper is called a constant number of times. If you derive the recursion tree of this function, you'll see that the longest path in this situation (number greater than one billion) is: helper(num > 10^9) is the first to be called, then helper(10^6 < num < 10^9) is called (from the else statement), then helper(10^3 < num < 10^6), then helper(10^2 < num < 10^3), then helper(20 < num < 10^2), and finally, helper(num < 20), when returns a string.


  • 10
    D

    Same concept. Combine belowTen and belowTwenty into LESS_THAN_20 array

    private final String[] LESS_THAN_20 = {"", "One", "Two", "Three", "Four", "Five", "Six", "Seven", "Eight", "Nine", "Ten", "Eleven", "Twelve", "Thirteen", "Fourteen", "Fifteen", "Sixteen", "Seventeen", "Eighteen", "Nineteen"};
    private final String[] TENS = {"", "Ten", "Twenty", "Thirty", "Forty", "Fifty", "Sixty", "Seventy", "Eighty", "Ninety"};
    
    public String numberToWords(int num) {
        if (num == 0) return  "Zero";
        return help(num);
    }
    
    String help(int num) {
        String ret = "";
        if (num < 20) {
            ret = LESS_THAN_20[num];
        } else if (num < 100) {
            ret = TENS[num / 10] + " " + help(num % 10);
        } else if (num < 1000) {
            ret = help(num / 100) + " Hundred " + help(num % 100);
        } else if (num < 1000000) {
            ret = help(num / 1000) + " Thousand " + help(num % 1000);
        } else if (num < 1000000000) {
            ret = help(num / 1000000) + " Million " + help(num % 1000000);
        } else {
            ret = help(num / 1000000000) + " Billion " + help(num % 1000000000);
        }
        return ret.trim();
    }

  • 1
    D

    @iuri.srb Why do you put empty string in belowTen and belowHundred?


  • 3
    I

    @DanielMan97 I put an empty string in belowTen in order to match the index 1 with string "One", index 2 with "Two", and so on. The same goes for belowHundred. For example, calling this function with the number 120 would append to the "result" variable, the following strings: "One" (120/100 = 1), "Hundred", "Twenty" and "" ("One Hundred Twenty"). If the initial number was 122, the strings would be "One", "Hundred", "Twenty" and "Two" ("One Hundred Twenty Two"). Writing the arrays that way simplifies the code and handles edge cases more easily.


  • 0
    S

    C# version

    public class Solution {
        List<string> _lessThan20 = new List<string>{string.Empty, "One", "Two", "Three", "Four", "Five", "Six", "Seven", "Eight", "Nine", "Ten",
            "Eleven", "Twelve", "Thirteen", "Fourteen", "Fifteen", "Sixteen", "Seventeen", "Eighteen", "Nineteen"};
        List<string> _tens = new List<string>{string.Empty, "Ten", "Twenty", "Thirty", "Forty", "Fifty", "Sixty", "Seventy", "Eighty", "Ninety"};
        
        public string NumberToWords(int num) 
        {
            if(num == 0)
                return "Zero";
            return Helper(num);
        }
        
        private string Helper(int num)
        {
            var sb = new StringBuilder();
            if(num<20)
            {
                sb.Append(_lessThan20[num]);
            }
            else if(num < 100)
            {
                sb.Append(_tens[num/10] + " ");
                sb.Append(_lessThan20[num%10]);
            }
            else if(num < 1000)
            {
                sb.Append(Helper(num/100) + " Hundred ");
                sb.Append(Helper(num%100));
            }
            else if(num < 1000000)
            {
                sb.Append(Helper(num/1000) + " Thousand ");
                sb.Append(Helper(num%1000));
            }
            else if(num < 1000000000)
            {
                sb.Append(Helper(num/1000000) + " Million ");
                sb.Append(Helper(num%1000000));
            }
            else
            {
                sb.Append(Helper(num/1000000000) + " Billion ");
                sb.Append(Helper(num%1000000000));
            }
            return sb.ToString().Trim();    
        }
    }
    

  • 0
    Y
    This post is deleted!

  • 0
    Y

    @da.lin.1232 My favorite solution so far I have seen including my own solution.


  • 0
    M

    amazing solution. however it may boost it a little if you use

            else if (num < 1000) s = belowTen[num/100] + " Hundred " + helper(num%100); //999
    
    

    instead of a recursive call


  • 0
    Y

    Please accept my knees.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.