LeetCode：273. 整数转换英文表示————困难

273. 整数转换英文表示
将非负整数 num 转换为其对应的英文表示。

示例 1：
输入：num = 123
输出："One Hundred Twenty Three"

示例 2：
输入：num = 12345
输出："Twelve Thousand Three Hundred Forty Five"

示例 3：
输入：num = 1234567
输出："One Million Two Hundred Thirty Four Thousand Five Hundred Sixty Seven"

示例 4：
输入：num = 1234567891
输出："One Billion Two Hundred Thirty Four Million Five Hundred Sixty Seven Thousand Eight Hundred Ninety One"
 

提示：
0 <= num <= 2的31次方 - 1

• 递归的做法。
• 由于最大的数字不超过2的31次方 - 1，所以最大的数字不超过10位数，我们可以按照3位数字一组来进行划分。
• 小于 20 的数可以直接得到其英文表示；大于等于 20 且小于 100 的数首先将十位转换成英文表示，然后对个位递归地转换成英文表示；大于等于 100 的数首先将百位转换成英文表示，然后对其余部分（十位和个位）递归地转换成英文表示。

bits = ['', 'One', 'Two', 'Three', 'Four', 'Five', 'Six', 'Seven', 'Eight', 'Nine']
ten = ['Ten', 'Eleven', 'Twelve', 'Thirteen', 'Fourteen', 'Fifteen', 'Sixteen', 'Seventeen', 'Eighteen', 'Nineteen']
tens = ['', 'Ten', 'Twenty', 'Thirty', 'Forty', 'Fifty', 'Sixty', 'Seventy', 'Eighty', 'Ninety']
thousands = ['', 'Thousand', 'Million', 'Billion']

class Solution:
    def numberToWords(self, num: int) -> str:
        if num == 0: return 'Zero'
        def func(num):
            s = ''
            if num == 0:
                return s
            elif num < 10:
                s += bits[num] + ' '
            elif num < 20:
                s += ten[num - 10] + ' '
            elif num < 100:
                s += tens[num // 10] + ' ' + func(num % 10)
            else:
                s += bits[num // 100] + ' Hundred ' + func(num % 100)
            return s


        s = ""
        begin = int(1e9) # 初始化1000000000
        for i in range(3, -1, -1):
            group = num // begin
            if group:
                num -= group * begin
                s += func(group) + thousands[i] + ' '
            begin //= 1000
        return s.strip()