LeetCode 面試題46. 把數(shù)字翻譯成字符串

面試題46. 把數(shù)字翻譯成字符串

題目來源：力扣（LeetCode）https://leetcode-cn.com/problems/ba-shu-zi-fan-yi-cheng-zi-fu-chuan-lcof

題目

給定一個數(shù)字，我們按照如下規(guī)則把它翻譯為字符串：0 翻譯成 “a” 麻敌，1 翻譯成 “b”愧驱，……芹血，11 翻譯成 “l(fā)”吕粹，……懂更，25 翻譯成 “z”碴卧。一個數(shù)字可能有多個翻譯。請編程實現(xiàn)一個函數(shù)鄙陡，用來計算一個數(shù)字有多少種不同的翻譯方法。

示例 1:

輸入: 12258
輸出: 5
解釋: 12258有5種不同的翻譯霹俺，分別是"bccfi", "bwfi", "bczi", "mcfi"和"mzi"

提示：

0 <= num < 231

解題思路

思路：動態(tài)規(guī)劃

先理清題意柔吼，題目中說明規(guī)則： 0 翻譯成 "a"， 1 翻譯成 "b"丙唧，...，25 翻譯成 "z"觅玻。而且題目中也說明【一個數(shù)字可能有多個翻譯】想际。那么這里就可以想到，當數(shù)字大于等于 10 小于等于 25 的時候溪厘，這部分的數(shù)字可以看出是兩個單獨數(shù)字組成胡本，或者單獨當成一個數(shù)字。

現(xiàn)在看示例 1：

輸入: 12258
輸出: 5
解釋: 12258有5種不同的翻譯畸悬，分別是"bccfi", "bwfi", "bczi", "mcfi"和"mzi"

看下面的解釋中侧甫，我們可以看到：

"bccfi" 這種情況就是將所有的數(shù)字單獨翻譯，即是 [1, 2 ,2, 5, 8]
剩下的 4 個就是連續(xù)兩位數(shù)字可考慮組合的情況
- [1, 22, 5, 8] 對應翻譯的是 "bwfi"
- [1, 2, 25, 8] 對應翻譯的是 "bczi"
- [12, 2, 5, 8] 對應翻譯的是 "mcfi"
- [12, 25, 8] 對應翻譯的是 "mzi"

在上面的示例中蹋宦，'58' 這個組合是不成立的披粟，我們知道組合的數(shù)字的范圍應該落在 [10, 25] 之間。

那么也就是說冷冗，翻譯的規(guī)則守屉，在字符串的第 i 個位置中可以分為兩種情況：

單獨進行翻譯
如果與 i - 1 位能夠組合成數(shù)字且落在 [10, 25]，那么可以連起來翻譯蒿辙。

現(xiàn)在假設(shè)將題目給出的數(shù)字 num 第 i 個數(shù)字記為 $x_i$ 拇泛，例如示例中的 num = 12258，那么 $x_1$ 就是 1思灌。

現(xiàn)在定義動態(tài)規(guī)劃列表 dp俺叭，假設(shè) dp[i] 為 $x_i$ 結(jié)尾的數(shù)字的翻譯方案。

按照前面得出的翻譯規(guī)則總結(jié)出轉(zhuǎn)移方程泰偿。

當 $x_{i-1}$ 和 $x_i$ 兩個數(shù)字組合可被翻譯時熄守，這里就會有兩種情況。單獨翻譯甜奄，或者組合翻譯柠横。也就是：

當組合翻譯的時候， $x_{i-1}x_i$ 組合確定课兄，前面 i-2 個數(shù)的翻譯方案為 dp[i-2]牍氛。
當單獨翻譯的時候， $x_i$ 確定烟阐，前面 i-1 個數(shù)的翻譯方案為 dp[i-1]搬俊。
也就是說當 $x_{i-1}$ 和 $x_i$ 兩個數(shù)字組合可被翻譯的時候紊扬，可由上述兩種情況結(jié)合，最終 dp[i] = dp[i-2] + dp[i-1]唉擂。

如果 $x_{i-1}$ 和 $x_i$ 兩個數(shù)字無法組合餐屎，那么就只能當成單個數(shù)字進行翻譯。所以 dp[i] = dp[i-1]玩祟。

這里需要注意的可組合數(shù)字落在的區(qū)間是 [10, 25]腹缩，前面已經(jīng)說明了，只有這種情況才能夠成功組合被翻譯空扎。

還有一種情況藏鹊，就是 $x_{i-1}$ 為 0 的時候，這種情況可以會出現(xiàn) 00, 01, 02, ... 這樣的組合數(shù)字转锈。但是這種情況是不能夠被翻譯的盘寡。

所以最終的狀態(tài)轉(zhuǎn)移方程，以及具體落在的區(qū)間：

$dp[i] = \begin{cases} dp[i-2] + dp[i-1]撮慨， & 10x_{i-1} + x_i \in [10, 25] \\ dp[i-1] & 10x_{i-1} + x_i \in [0, 10) \bigcup (25, 99] \end{cases}$

注意竿痰，這里我們并不考慮三位數(shù)的組合

在這里，dp[i] 表示的是以 $x_i$ 結(jié)尾的數(shù)字的翻譯方案砌溺。當 i=0 和 i=1 的時候影涉，表示的是【無數(shù)字】和【第一個數(shù)字】。這里都初始化為 1抚吠。（前面說明了 $x_1$ 表示的是第 1 個數(shù)字常潮，如題目 12258 中的第一個數(shù)字 1。）

反向推導 dp[0] 的值楷力，假設(shè)當出現(xiàn)兩個數(shù)字能夠組合且被翻譯的情況下喊式，例如 12，那么 dp[2] 顯然是等于 2萧朝。要么以 [1, 2] 的形式岔留，要么以 [12] 的形式進行翻譯。
此時 dp[2] = dp[1] + dp[0] = 2检柬，而 dp[1] 為 1献联，那么 dp[0] = 1。

而最終我們需要求得的結(jié)果就是 dp[n]何址，也就是題目中所需求的翻譯方案（n 表示的是數(shù)字長度里逆。）

在這里可以使用字符串截取的方法去實現(xiàn)，這里需要將數(shù)字下轉(zhuǎn)換為字符串用爪，缺點是字符串會占用一定的空間原押。這里采用字符串截取的方法來求解。還有一種方法是使用取模的方法（可考慮嘗試）

具體的代碼如下偎血。

代碼實現(xiàn)

class Solution:
    def translateNum(self, num: int) -> int:
        string = str(num)
        n = len(string)

        dp = [0] * (n+1)
        
        dp[0]=1
        dp[1]=1

        for i in range(2, n + 1):
            if "10" <= string[i-2:i] <="25":
                dp[i] = dp[i-1] + dp[i-2]
            else:
                dp[i] = dp[i-1]
        
        return dp[n]

實現(xiàn)結(jié)果

總結(jié)

本題使用的動態(tài)規(guī)劃诸衔，先分析題意盯漂，找出翻譯的規(guī)則”颗可以發(fā)現(xiàn)就缆，當?shù)?i 個數(shù)字被翻譯的時候，可能出現(xiàn)兩種情況：
- 單獨翻譯第 i 個位置的數(shù)字
- 當?shù)?i 個位置的數(shù)字與第 i-1 位置的數(shù)字組合且可被翻譯谒亦，那么可考慮組合進行翻譯
根據(jù)上面的翻譯規(guī)則竭宰，可以求得轉(zhuǎn)移方程(具體參考上面的解析)：
- 當兩個連續(xù)數(shù)字能夠組合的情況下：dp[i] = dp[i-2]+dp[i-1]
- 否則：dp[i]=dp[i-1]
對動態(tài)規(guī)劃列表進行初始化，確定最終求解的值為 dp[n]诊霹。

LeetCode 面試題46. 把數(shù)字翻譯成字符串 | Python