題目連結：
題目意譯：
一個包含著 A 到 Z 的字母之訊息可以被加密成數字藉由以下的映射：
'A' -> "1"
'B' -> "2"
……
'Z' -> "26"
為了解密一個加密訊息，所有數字必須分組並映射回對應的字母藉由翻轉以上的映射關係（可能會有多種方式解密）。例如，"11106" 可以映射為
"AAJF" 其數字分組為 (1 1 10 6)
"KJF" 其數字分組為 (11 10 6)
注意到數字分組 (1 11 06) 是不合法的，原因是 "06" 不能映射到 'F' 因為 "6" 與 "06" 不同。
除了以上的映射以外，一個加密訊息可能包含 '*' 字元，其可以代表 '1' 到 '9'的任意數字（'0' 除外）。例如，加密訊息 "1*" 可能代表加密訊息 "11" 、 "12" 、 "13" 、 "14" 、 "15" 、 "16" 、 "17" 、 "18" 或是 "19" 中的一者。解密 "1*" 等價於解密其所能表示的加密訊息的任何一者。
給定一個字串 s 包含著數字以及 '*' 字元，回傳其解密的方法數。
由於答案可能會很大，將其模 10 ^ 9 + 7 後回傳。
限制：
1 ≦ s.length ≦ 10 ^ 5
s[i] 為數字或是 '*'。
範例測資：
範例 1：
輸入： s = "*"
輸出： 9
解釋： 加密訊息可以表示訊息 "1" 、 "2" 、 "3" 、 "4" 、 "5" 、 "6" 、 "7" 、 "8" 或是 "9" 中的一者。
每個依序可以解密為字串 "A" 、 "B" 、 "C" 、 "D" 、 "E" 、 "F" 、 "G" 、 "H" 和 "I"。
因此，總共有 9 種方式解密 "*"。
範例 2：
輸入： s = "1*"
輸出： 18
解釋： 加密訊息可以表示訊息 "11" 、 "12" 、 "13" 、 "14" 、 "15" 、 "16" 、 "17" 、 "18" 或是 "19" 中的一者。
每個都有 2 種方式可以解密（例如 "11" 可以解密為 "AA" 或是 "K"）
因此，總共有 9 × 2 = 18 種方式解密 "1*"。
範例 3：
輸入： s = "2*"
輸出： 15
解釋： 加密訊息可以表示訊息 "21" 、 "22" 、 "23" 、 "24" 、 "25" 、 "26" 、 "27" 、 "28" 或是 "29" 中的一者。
"21" 、 "22" 、 "23" 、 "24" 、 "25" 和 "26" 有兩種方式可以被解密，但是 "27" 、 "28" 和 "29" 只有一種方式。
因此，總共有 (6 × 2) + (3 × 1) = 12 + 3 = 15 種方式解密 "2*"。
解題思維：
動態規劃（Dynamic Programming）即可。
定義一個陣列 D，其中 D[i] 代表 s 前 i 個字元（注意，字串 s 本身的索引值從 0 開始，因此前 i 個字元代表 s[0] ～ s[i - 1]）可以有多少種解密之方法數。可以看到其遞迴式為：
D[0] = 1，因為什麼都沒有也就不會有解密失敗的問題，因此只有一種解密方式，也就是什麼都沒有；
當 i = 1，會有以下三種情況：
1. s[0] 是 '*' 時，代表可以任意地將其解密為 1 ～ 9。因此 D[1] = 9；
2. s[0] 不為 '0' 時，代表只有那一種選擇（即 s[0] 的數字）可以映射。因此 D[1] = 1；
3. s[0] 為 '0' 時，此時沒有任何可行的映射。因此 D[1] = 0。
剩下的 i > 1 之情況，會有以下三種情況：
一：當 s[i - 1] 為 '*'，則又有以下四種子情況：
1. s[i - 2]（即前一個字元）為 '*' 時，代表 s[i - 2] 可以和 s[i - 1] 結合（也可以選擇不結合）並產生 "11" ～ "26" （除了 "20"）之額外編號。因此 D[i] = D[i - 1] × 9 + D[i - 2] × 15（代表結合），加號左側代表不結合兩字元、右側代表結合；
2. s[i - 2] 為 '1' 時，代表可以類似上面結合出額外的 "11" ～ "19"。因此 D[i] = D[i - 1] × 9 + D[i - 2] × 9；
3. s[i - 2] 為 '2' 時，代表可以結合出額外的 "21" ～ "26"。因此 D[i] = D[i - 1] × 9 + D[i - 2] × 6；
4. 以上皆非。因此此時 s[i - 1] 不能跟前一個字元配對，因此 D[i] = D[i - 1] × 9。
二：當 s[i - 1] 不為 '0'（假設其為 X），則又有以下五種子情況：
1. s[i - 2] 為 '*' 且 X ≦ 6 時，代表我們可以結合兩字元產生 "1X" 和 "2X" 兩種編碼。因此，D[i] = D[i - 1] + D[i - 2] × 2，同樣地，加號左側代表不結合兩字元、右側代表結合；
2. s[i - 2] 為 '*' 且 X > 6 時，代表我們可以結合產生 "1X" 這個編碼。因此 D[i] = D[i - 1] + D[i - 2]；
3. s[i - 2] 為 '2' 且 X ≦ 6 時，代表我們可以產生 "2X"。因此 D[i] = D[i - 1] + D[i - 2]；
4. s[i - 1] 為 '1' 時，代表我們可以產生出 "1X"。因此 D[i] = D[i - 1] + D[i - 2]；
5. 以上皆非，則代表我們只能單獨地解密當前字元。因此 D[i] = D[i - 1]。
三：當 s[i - 1] 為 '0'，則又有以下四種子情況：
1. s[i - 2] 為 '*' 時，代表我們可以結合兩字元產生 "10" 和 "20" 兩種編碼。但是此時因為 s[i - 1] 是 '0'，我們不能單獨地解密該字元。因此，D[i] = D[i - 2] × 2；
2. s[i - 2] 為 '2' 時，代表我們可以結合兩字元產生 "20"。因此 D[i] = D[i - 2]；
3. s[i - 1] 為 '1' 時，代表我們可以結合兩字元產生 "10"。因此 D[i] = D[i - 2]；
4. 以上皆非，則代表我們既不能解密當前字元也不能與前一字元結合，因此 D[i] = 0。
有了以上遞迴式後，接著我們從 i = 1 開始掃到 i = s.length 並套用以上的求 D[i] 值之方法即可（但是記得每次求值時需一直取除以 10 ^ 9 + 7 的餘數以免溢位）。而所求將為 D[s.length]。
可以看到實際上不難，只是要考慮的情況真的有點多。
此次分享到此為止，如有任何更加簡潔的想法或是有說明不清楚之地方，也煩請各位大大撥冗討論。
