273. Integer to English Words
这道题有点考基本功的意思, 大概提交了四五次AC了，还是有点成就感的

class Solution(object):
    def numberToWords(self, num):
        """
        :type num: int
        :rtype: str
        """
        self.h = ["Thousand", "Million", "Billion"]
        if num == 0:
            return "Zero"
        #if 
        return " ".join(self.dfs(num, 0))
    
    def dfs(self, num, counter):
        new = num % 1000
        num = num / 1000
        if num > 0:
            if new > 0:
                if num % 1000:
                    return self.dfs(num, counter+1) + [self.h[counter]] + self.say(new)
                else:
                    return self.dfs(num, counter+1) + self.say(new)
            else:
                val = self.dfs(num, counter+1)
                if num % 1000:
                    return val + [self.h[counter]]
                else:
                    return val
        else:
            return self.say(new)
    
    def say(self, num): # deal with number less than 1000
        m = {1: "One",
             2: "Two",
             3: "Three",
             4: "Four",
             5: "Five",
             6: "Six",
             7: "Seven",
             8: "Eight",
             9: "Nine",
             10: "Ten",
             11: "Eleven",
             12: "Twelve",
             13: "Thirteen",
             14: "Fourteen",
             15: "Fifteen",
             16: "Sixteen",
             17: "Seventeen",
             18: "Eighteen",
             19: "Nineteen",
             20: "Twenty",
             30: "Thirty",
             40: "Forty",
             50: "Fifty",
             60: "Sixty",
             70: "Seventy",
             80: "Eighty",
             90: "Ninety"
            }
        hundred = num / 100
        res = []
        if hundred:
            res += [m[hundred],  "Hundred"]
        left = num % 100
        if left > 0:
            if left in m:
                res += [m[left]]
            else:
                res += [m[left/10*10], m[left%10]]
        return res