Recursive Python


  • 37
    def numberToWords(self, num):
        to19 = 'One Two Three Four Five Six Seven Eight Nine Ten Eleven Twelve ' \
               'Thirteen Fourteen Fifteen Sixteen Seventeen Eighteen Nineteen'.split()
        tens = 'Twenty Thirty Forty Fifty Sixty Seventy Eighty Ninety'.split()
        def words(n):
            if n < 20:
                return to19[n-1:n]
            if n < 100:
                return [tens[n/10-2]] + words(n%10)
            if n < 1000:
                return [to19[n/100-1]] + ['Hundred'] + words(n%100)
            for p, w in enumerate(('Thousand', 'Million', 'Billion'), 1):
                if n < 1000**(p+1):
                    return words(n/1000**p) + [w] + words(n%1000**p)
        return ' '.join(words(num)) or 'Zero'

  • 0

    clear and concise :)


  • 4

    Hi, Stefan. Well, I have been waiting for your post since the problem is published as I believe you will have a very concise way to solve the problem in short codes. It does :-)


  • 0
    N

    i found you !


  • 0

    With a little bit of math you don't need to loop but maybe the loop is easier to read?
    https://discuss.leetcode.com/topic/68311/short-clean-java-solution-using-math-log10-and-math-pow


  • 0

    Very brilliant solution to use recursion, so the code is clean.

    This is just a re-write in C++, which also shows how convenient Python is in term of string manipulation :-)

        typedef vector<string> VS;    
        VS to19 = { "One", "Two", "Three", "Four", "Five", "Six", "Seven", "Eight", "Nine", "Ten", "Eleven", "Twelve", 
                  "Thirteen", "Fourteen", "Fifteen", "Sixteen", "Seventeen", "Eighteen", "Nineteen"};
        VS tens = { "Twenty", "Thirty", "Forty", "Fifty", "Sixty", "Seventy", "Eighty", "Ninety" };
        VS units = {"Thousand", "Million", "Billion"};
    
        VS join(const VS& w1, const VS& w2) {
            VS w(w1); w.insert(w.end(), w2.begin(), w2.end());
            return w;
        }
        
        string numberToWords(int n) {
            VS ws(words(n));
            if (ws.empty()) return "Zero";
            string res;
            for (auto& w : ws) res += (w + " ");
            return res.substr(0, res.size()-1);
        }
        
        VS words(int n) {
            if (n == 0) return { };
            if (n < 20) return { to19[n-1] };
            if (n < 100) return join({ tens[n/10-2] }, words(n%10));
            if (n < 1000) return join(join({ to19[n/100-1] }, { "Hundred" }), words(n%100));
            
            int base = 1000;
            for (auto unit : units) {
                if (unit == "Billion" or n < 1000*base) return join(join(words(n/base), {unit}), words(n%base));
                base *= 1000;
            }
        }
    

Log in to reply
 

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