遞迴應用: 把 數字 轉成 英文表示法 Integer to English Words_Leetcode #273

Stephanie Klepacki on Unsplash

題目敘述 Integer to English Words

給定一個整數num

請轉換成對應的的英文數字表達(One, Two, Three, ... 那種數字表達式)

測試範例:

Example 1:

Input: num = 123
Output: "One Hundred Twenty Three"

Example 2:

Input: num = 12345
Output: "Twelve Thousand Three Hundred Forty Five"

Example 3:

Input: num = 1234567
Output: "One Million Two Hundred Thirty Four Thousand Five Hundred Sixty Seven"
 

約束條件

Constraints:

• 0 <= num <= 2^31 - 1

輸入的整數是32bit整數範圍內

觀察 英文數字表達式的範圍

大方向是3位數一組，區分為 千Thousand、百萬Million、十億Billion

對應到10^3, 10^6, 10^9

小細節是未滿20的小數字，英文有專門一一對應的稱呼

1 One

2 Two

3 Three

...

10 Ten

11 Eleven

12 Twelve

...

19 Nineteen

另外，20, 30, 40, ..., 90 有各自的稱呼

20 Twenty

30 Thirty

40 Forty

...

90 Ninety

演算法 遞迴分解

承接觀察點的思考

逢三位數分解一次，對應到千Thousand、百萬Million、十億Billion。

接著特別針對小區間1~19 還有 20, 30, 40, ..., 90 的數字進行特別處理。

從高位數往低位數分解，找到對應的英文單字，分解到零的時候，整個轉換過程結束。

程式碼 遞迴分解

class Solution:
    def numberToWords(self, num):
    
        small_number = '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 small_number[n-1:n]

            elif n < 100:
                return [ tens[n//10 - 2] ] + words(n%10)

            elif n < 1000:
                return [ small_number[n//100-1] ] + ['Hundred'] + words(n%100)

            else:
                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'

複雜度分析

時間複雜度: O(log n)

整數n用十進位表達，最多需要log10 n個數字，至多log n回合可以轉換完畢。

空間複雜度: O(log n)

整數n用十進位表達，最多需要log10 n個數字，至多log n回合可以轉換完畢。

遞迴深度最深為O( log n)

Reference

[1] Integer to English Words - LeetCode