273. Integer to English Words

[tech-cow]

'''
[8:41] Start

Thoughts (Didn't execute since not sure?):
    Use a stack, and looking @ elements from the end
    Having a hashmap
        {
            key                      |       val
            reverse index of input   |    assoicated english words (ex: "hundred", "thousand")
        }
    manually input some logic around index
    
    
        
[8:44] a bit cancer, give up | Solution Checking & retrospect

[8:44 - 10:52] Eat, Shower, think about this shit, and having brain fart but finally crack it

[10:53] Start Coding again

Problem Soving:
    1. digits rules : name changes every thousands
        1,000,000,000
        b   m   t

    2. Using divide and conquer to continue breaking large number to smaller instance
        and have a few base case to handle any numbers smaller than hundreds
      
[11:41] FUCK it, so many edge case... why?
'''

# dfs: make sure to keep track of parameter passing 
class Solution(object):
    def numberToWords(self, num):
        less_than_20 = ["", "One", "Two", "Three", "Four", "Five", "Six", "Seven", "Eight", "Nine", "Ten", "Eleven", "Twelve", "Thirteen", "Fourteen", "Fifteen", "Sixteen", "Seventeen", "Eighteen", "Nineteen", "Twenty"]
        tens = ["", "Ten", "Twenty", "Thirty", "Forty", "Fifty", "Sixty", "Seventy", "Eighty", "Ninety"]
        thousands = ["" , "Thousand", "Million", "Billion"]

        res = ""
        if num == 0: return "Zero"
        for i in range(len(thousands)):
            if num % 1000 != 0:
                res = self.dfsHelper(num % 1000, less_than_20, tens).strip() + " " +  thousands[i] + " " + res
            num //= 1000
        return res.strip()

    def dfsHelper(self, num, less_than_20, tens):
        if num < 20:
           return less_than_20[num] 
        elif 20 <= num < 100:
            return tens[num // 10] + " " + less_than_20[num % 10]
        elif 100 <= num <= 999:
            return less_than_20[num // 100] + " Hundred " + self.dfsHelper(num % 100, less_than_20, tens)