點擊上方「程式設計師大白」，選擇「星標」公眾號
重磅乾貨，第一時間送達
題意題目：路徑解碼 一條包含A - Z字符的信息被使用如下規則進行編碼：
'A' -> 1
'B' -> 2
...
'Z' -> 26給定一條編碼好的數字串，確定總的解碼方法數. 舉個例子，給定編碼好的信息"12"，可以被解碼為AB"(1 2)或者"L"(12).因此，這個總的解碼數量是2.
題解算法及複雜度（0 ms） 本題和爬梯子（第70題）那個題有點像，仔細考慮一下看看是不是這樣. 每個英文字母最多用兩個數字進行編碼，也就是在解碼的時候，每次使用一個數字或者兩個數字進行解碼.換一種說法，對前i個數字解碼可以轉化為：在前i-2個數字已經解碼的基礎上，把(i-1, i)解碼成一個字母，或者在前i-1個數字已經解碼的基礎上，把(i)轉化為一個字母. 根據以上分析，假如把dp[i]來表示以從0到第i個數字的數字串的解碼方法數，那麼dp[i]可以從dp[i - 1]和dp[i - 2]得到.這個轉移過程暗示動態規划過程中的最優子結構性質. 對狀態轉移過程進行分析，分析狀態轉移過程需要滿足的條件(這一部分靠細心吧)：
先求出來原數字串中第i-1和第i個數字代表的真實數值，定義為value，則有
dp[i] = dp[i - 1] 0 < value < 10
dp[i] = dp[i - 2] value = 10 or 20
dp[i] = dp[i - 1] + dp[i - 2] 10 < value < 20 or 20 < value <= 26以上過程可以自己簡單畫一個數軸分析一下. 根據以上過程進行編碼提交，發現發揮一個Wrong Answer，而錯誤的數據是"100"，經過分析發現，題意可能存在一點問題，本題題意是給定編碼好的信息，來進行解碼，所以至少存在一種解碼方式，可是進行提交會發現，存在有的給定的編碼好的信息的解碼方式為0，也就是給定的數字串無法進行解碼，與題意似乎有點矛盾.這裡注意一下. 但是為了AC掉這個題目，對自己的答案還是進行了補充，也就是，當value % 10 == 0 && value / 10 != 1 && value / 10 != 2時，直接返回0，經過補充之後，可以順利進行AC. 時間複雜度: O(n). n是數字串的長度，根據以上算法可以知道，數字串只需要遍歷一遍即可得到結果. 代碼參見本文件夾下solution.cpp
算法正確性舉個例子
//輸入數據，s = "101"
//初始化dp[0] = dp[1] = 1
// i = 2, value = (s[i - 2] - '0') * 10 + s[i - 1] - '0' = 10
dp[i] = dp[i - 2] = 1
// i = 3, value = (s[i - 2] - '0') * 10 + s[i - 1] - '0' = 1
dp[i] = dp[i - 1] = 1CPP代碼
class Solution {
public:
int numDecodings(string s) {
int len = s.length();
if(len == 0 || s[0] == '0') return 0;
vector<int>dp(len + 1);
dp[0] = 1;dp[1] = 1;
for(int i = 2; i <= len; i ++ ){
int value = (s[i - 2] - '0') * 10 + s[i - 1] - '0';
if(value % 10 == 0) {
int temp = value / 10;
if(temp == 1 || temp == 2) {
dp[i] = dp[i - 2];
} else {
return 0;
}
} else {
if(value < 10 || value > 26) {
dp[i] = dp[i - 1];
} else {
dp[i] = dp[i - 1] + dp[i - 2];
}
}
}
return dp[len];
}
};重磅！程式設計師大白交流群-學術微信交流群已成立
額外贈送福利資源！邱錫鵬深度學習與神經網絡，pytorch官方中文教程，利用Python進行數據分析，機器學習學習筆記，pandas官方文檔中文版，effective java（中文版）等20項福利資源
獲取方式：進入群後點開群公告即可領取下載連結
拉人小助手出了問題，最近不能使用，請大家加入微信2群
注意：請大家添加時修改備註為 [學校/公司 + 姓名 + 方向]
例如 —— 哈工大+張三+對話系統。
號主，微商請自覺繞道。謝謝！
推薦閱讀
Leetcode題解 SimplifyPath
Leetcode題解 InsertInterval
Leetcode題解 MergeIntervals
Leetcode題解 JumpGame
Leetcode題解 N-Queens
Leetcode題解 Trapping Rain Water
關於程式設計師大白
程式設計師大白是一群哈工大，東北大學，西湖大學和上海交通大學的碩士博士運營維護的號，大家樂於分享高質量文章，喜歡總結知識，歡迎關注[程式設計師大白]，大家一起學習進步！