九章演算法 | Google 面試題：解碼方法2

撰文 | JZ

專欄 | 九章演算法

題目描述

一個包含A到Z的消息通過如下方式加密：

A -> 1

除了上述規則外，加密字元串還可能包含字元*，可以將其視為一個1到9之間的數字字元。給定一個包含數字字元和*的加密信息，問有幾種解碼方式。由於答案可能很大，只需返回答案對10^9+7取模後的結果即可。

樣例1:

輸入: "*"輸出: 9說明: 該加密信息可解碼為這些字元串："A", "B", "C", "D", "E", "F", "G", "H", "I"。

樣例2:

輸入: "1*"輸出: 18說明: "1*"可以表示"11"、"12"、……、"19"，每種表示都既可以解碼成單個字元，也可以解碼成兩個字元，答案為9+9=18。

解題思路分析

這道題算是 解碼方法1 的follow up，區別在於加入了一個通配符*可以用劃分型動態規劃解決，因為對於一個加密字元串，將其最後一位單獨劃分出來，該位的解碼方案數與前面剩下的字元串的解碼方案數互不影響，相互獨立，將兩者相乘即可得到這種情況的方案總數，再考慮將最後兩位單獨劃分出來解碼為一個字元的的情況，用同樣的方法得到方案數，將兩者相加即可得到原問題的總方案數。在 解碼方法 中，考慮當前位是單獨解碼成一個字元還是與前一位一起解碼成一個字元，在這題中，也是進行相同的考慮，只不過面對的情況多一點而已。

狀態表示以及初始化：設加密字元串為s，s的第i位為s[i-1]，f[i]表示s的前i個字元的解碼方式的數量，f[0]=1

狀態轉移：

s[i-1]單獨解碼成一個字元：

s[i-1]為數字字元：若s[i-1]==0，則s[i-1]不能單獨解碼為一個字元，對f[i]的貢獻為0；若s[i-1]!=0，則s[i-1]可以解碼為一個字元，同時，前i-1位有f[i-1]種解碼方式，這種情況對f[i]的貢獻為f[i-1]。

s[i-1]==*：s[i-1]可以解碼成一個字元而且有9種可能，對於每一種可能，前i-1位都有f[i-1]中解碼方式，故這種情況共有9*f[i-1]中解碼方式。

s[i-2]和s[i-1]一起解碼成一個字元：

s[i-2]和s[i-1]都是數字字元：若組成的數字不在10到26之間，則s[i-2]和s[i-1]不能一起解碼成一個字元，對f[i]的貢獻為0；否則，s[i-2]和s[i-1]可以一起解碼成一個字元，對f[i]的貢獻為f[i-2]。

若s[i-1]==*，s[i-2]為數字字元：這種情況下，只有"1*"和"2*"可以解碼成一個字元，所以若s[i-2]不為1或者2，那麼s[i-2]和s[i-1]不能一起解碼成一個字元，對答案的貢獻為0；若s[i-2]==1，則"1*"可以表示成"11"、"12"、……、"19"，解碼為"K"到"S"，共9種可能，對於每一種可能，前i-2位都有f[i-2]種解碼方式，貢獻為9*f[i-2]；若s[i-2]==2，則"2*"可以表示成"21"、"22"、"23"、"24"、"25"、"26"可以解碼成一個字元，共6種可能，同樣的，其貢獻為6*f[i-2]。

若s[i-2]==*，s[i-1]為數字字元：同樣考慮這兩位形成的數字可能的範圍(10~26)。若s[i-1]在0到6之間，那麼s[i-2]可以取1或2兩種可能，對f[i]的貢獻為2*f[i-2]；若s[i-1]在7到』9『之間，那麼s[i-1]只能取1，否則是無法將兩個字元一起解碼成一個字元的，對f[i]的貢獻為f[i-2]。

若s[i-2]和s[i-1]均為*："**"，由於*可以表示為1到9，而要解碼成一個字元要求數字範圍在10~26，故解碼成一個字元的方法有15種，即11~19以及21~26，對f[i]的貢獻為15*f[i-2]。

所有涉及的計算都應該對10^9+7取模，並且注意到有乘法可能會使中間結果溢出32位整數，計算時應進行類型轉換。最後答案為f[n]，n為加密字元串的長度。演算法的時間複雜度為O(n)，空間複雜度為O(n)。

參考程序

九章演算法 - 幫助更多中國人找到好工作，矽谷頂尖IT企業工程師實時在線授課為你傳授面試技巧

面試官角度分析

這道題是劃分型動態規劃的題目，當加入*後題目變得稍微複雜，但基本思想仍是一樣的，仔細分析可能的各種情況即可。題目難點在於狀態轉移時情況繁多，需要cover所有可能出現的case，給出正確的解法可以hire。

lintcode相關問題

解碼方法