題目
A message containing letters from A-Z is being encoded to numbers using the following mapping way:
'A' -> 1
'B' -> 2
...
'Z' -> 26
Beyond that, now the encoded string can also contain the character '*', which can be treated as one of the numbers from 1 to 9.
Given the encoded message containing digits and the character '*', return the total number of ways to decode it.
Also, since the answer may be very large, you should return the output mod 109 + 7.
Example 1:
Input: ""
Output: 9
Explanation: The encoded message can be decoded to the string: "A", "B", "C", "D", "E", "F", "G", "H", "I".
Example 2:
Input: "1"
Output: 9 + 9 = 18
Note:
The length of the input string will fit in range [1, 105].
The input string will only contain the character '*' and digits '0' - '9'.
編碼方式如下：
- 1 ~ 26 分別映射 "A" ~ "Z"
- "*" 可以代指 0 ~ 9
給出一組長度為 [1,105] 的數字字符串把曼，求可以有多少種解碼方式线梗。
解題思路
一個數字字符串燎竖，如果只考慮 0 ~ 9，沒有 * ，則編碼方式只有一種唉匾，在本題中由于將范圍擴大到了 [1,26]，且還有 * 插入，所以我們只需要針對字符串中的 1 剧浸、2、*進行針對處理即可矗钟。
以 6219 為例唆香，62 和 621 分別有 1、2
假設當前字符串 sub[0,n-1] 吨艇、 sub[0,n] 有 i躬它、j 種編碼方式，若 sub[0,n] 的末尾字符為 1 东涡，則 sub[0,n+1] 計算時可分為兩種情況(sub[0,n+1] 的末尾字符為 subn+1)：
- subn+1 單獨進行解碼時冯吓，編碼方式有 j 種
- subn+1 與 subn 進行合并解碼時倘待，編碼方式有 i 種
所以 sub[0,n+1] = j + i = str[0,n] + str[0,n-1]。
在此基礎上需要做一些區(qū)分的注意：
- 若subn+1 為 0 组贺，則只能與 subn 進行合并解碼延柠，不能單獨解碼。
- subn == 1锣披，2 時贞间，subn+1 在 [0,9]，[0,6] 范圍內雹仿，才能與 subn 進行合并解碼增热。
- subn == * 時，由于 * 代指 [0,9]胧辽，所以 subn+1 單獨解碼的方式 9 倍峻仇，合并解碼時， 位數為 1 時解碼方式 9 倍邑商，尾數為 2 時解碼方式 6 倍摄咆。
代碼實現
Runtime: 100 ms
Memory: 20.5 MB
func numDecodings(_ s: String) -> Int {
//字符串一共有多少種解碼方式
var e0:Int64 = 1
//存儲字符串末位為 1 時的編碼方式數量
var e1:Int64 = 0
//存儲字符串末位為 1 時的編碼方式數量
var e2:Int64 = 0
//臨時計算用的容器
var f0:Int64 = 0
//模的除數
let M:Int64 = Int64(1e9 + 7)
//遍歷字符串 s
for c in s
{
if c == "*"
{
//由于 * 可以代指 1 ~ 9
//所以 e0 和 e1 都有九種方式，而最大到 26 所以 e2 只有 6 種
f0 = 9 * e0 + 9 * e1 + 6 * e2
//由于 * 可以代指 1 和 2人断，所以 e1 和 e2 都需要賦值
e1 = e0
e2 = e0
}
else
{
//先計算合并解碼的情況
//當前一位為 1 時吭从，當前位在[0,9]范圍內都可以進行合并解碼，所以將 e1 加入到容器
f0 = e1
//當前一位為 2 時恶迈，當前位在[0,6]范圍內才可以進行合并解碼涩金，將 e2 加入到容器
if c <= "6"
{
f0 += e2
}
//計算單獨解碼
//如果當前字符為 0 ，則不能進行單獨解碼
//所以只有當前位在[1,9]范圍內才可以單獨解碼暇仲，將 e0 加入到容器
if c > "0"
{
f0 += e0
}
//依據當前字符是否為 1 或 2 步做，來判斷是將 e1 e2 為 e0 還是 0
//以 61616 為例，當循環(huán)到 6161 時奈附，當前字符為 1
//在下次遍歷到 6 時全度，由于會用到 616 和 6161 的結果
//所以在此次遍歷中，將 e0 賦值給 e1
//這樣斥滤，e1 中保留的就是 616 的結果将鸵，而 6161 的結果可在之后通過 f0 進行計算存儲到 e0 中
//當前字符不為 1 時，則下次遍歷不會出現變動中跌，故將 e1 變更為 0
// e2 也是相同道理
e1 = c == "1" ? e0 : 0
e2 = c == "2" ? e0 : 0
}
//本次循環(huán)中咨堤，用 f0 % M 得出結果 e0
e0 = f0 % M
}
//返回結果
return Int(e0)
}
