題目描述
給定一個數字，我們按照如下規則把它翻譯為字串：0 翻譯成 “a” ，1 翻譯成 “b”，……，11 翻譯成 “l”，……，25 翻譯成 “z”。一個數字可能有多個翻譯。請程式設計實現一個函式，用來計算一個數字有多少種不同的翻譯方法。
示例 1：
輸入： 12258
輸出： 5
解釋： 12258 有 5 種不同的翻譯，分別是 “bccfi”， “bwfi”， “bczi”， “mcfi” 和 “mzi”
提示：0 <= num < 2^31
題目連結：https：//leetcode-cn。com/problems/ba-shu-zi-fan-yi-cheng-zi-fu-chuan-lcof/
翻譯規則
解題思路
一、動態規劃
首先把輸入的數字轉字串 numStr，定義一個數組 dp ［numStr。length］，dp ［i］ 表示子串 numStr ［0， i+1］ 有多少種不同的翻譯。因為子串 numStr ［0， 1］ 只有一個字元，肯定只有一種翻譯，所以初始化 dp ［0］ = 1，對於 i > 0 以後的子串 numStr ［0， i+1］，我們將子串 numStr ［i-1， i+1］ 轉換為數字 subInt，有以下兩種情況：
當 10 <= subInt <= 25，說明 numStr ［0， i+1］ 這個子串可以由 子串 numStr ［0， i］ 的翻譯方式 + “x” 或者透過子串 numStr ［0， i-1］ 的翻譯方式 + “xx” 這兩種形式來表示。所以 dp ［i］ = dp ［i-1］ + dp ［i-2］。
當 subInt <10 或者 subInt> 25 時，說明 numStr ［0， i+1］ 這個子串只能透過 numStr ［0， i］ 的翻譯方式 + “x” 這種形式來表示，所以 dp ［i］ = dp ［i-1］。
比如說 12258 這個數字，其對應的 dp 陣列如下：
public int translateNum（int num） { String numStr = Integer。toString（num）； int［］ dp = new int［numStr。length（）］； dp［0］ = 1； for （int i = 1； i < dp。length； i++） { String sub = numStr。substring（i - 1， i + 1）； int subInt = Integer。parseInt（sub）； if （subInt <= 25 && subInt >= 10） { if （i - 2 >= 0） { dp［i］ = dp［i - 1］ + dp［i - 2］； } else { dp［i］ = dp［i - 1］ + 1； } } else { dp［i］ = dp［i - 1］； } } return dp［dp。length - 1］；}
影片講解
在 YouTube 上檢視請點選 https：//youtu。be/RiwKtdWJvms
在 B 站上檢視請點選 https：//www。bilibili。com/video/BV1HZ4y1H7md
在西瓜影片上檢視請點選 https：//www。ixigua。com/i6837810836044513795
版權宣告
本文作者：
WG
本文連結：
https：//wglog。net/2020/06/10/ba-shu-zi-fan-yi-cheng-zi-fu-chuan-lcof/
版權宣告：
本部落格所有文章除特別宣告外，均採用 BY 許可協議。轉載請註明出處！
# 演算法 # 動態規劃 # 字串
