題目鏈接
tag:
- Medium；
question：
??A message containing letters from A-Z is being encoded to numbers using the following mapping:
'A' -> 1
'B' -> 2
...
'Z' -> 26
Given a non-empty string containing only digits, determine the total number of ways to decode it.
Example 1:
Input: "12"
Output: 2
Explanation: It could be decoded as "AB" (1 2) or "L" (12).
Example 2:
Input: "226"
Output: 3
Explanation: It could be decoded as "BZ" (2 26), "VF" (22 6), or "BBF" (2 2 6).
思路：
??這道題要求解碼方法纯命，跟之前那道 Climbing Stairs 爬梯子問題 非常的相似宴胧，但是還有一些其他的限制條件，比如說一位數(shù)時(shí)不能為0焕梅，兩位數(shù)不能大于26乡数，其十位上的數(shù)也不能為0晚唇，出去這些限制條件织盼，根爬梯子基本沒啥區(qū)別，也勉強(qiáng)算特殊的斐波那契數(shù)列酱塔，當(dāng)然需要用動(dòng)態(tài)規(guī)劃Dynamci Programming來解沥邻。建立一位dp數(shù)組，長(zhǎng)度比輸入數(shù)組長(zhǎng)多多2羊娃，全部初始化為1唐全，因?yàn)殪巢瞧鯏?shù)列的前兩項(xiàng)也為1，然后從第三個(gè)數(shù)開始更新蕊玷，對(duì)應(yīng)數(shù)組的第一個(gè)數(shù)邮利。對(duì)每個(gè)數(shù)組首先判斷其是否為0，若是將改為dp賦0垃帅，若不是延届，賦上一個(gè)dp值，此時(shí)相當(dāng)如加上了dp[i - 1], 然后看數(shù)組前一位是否存在贸诚，如果存在且滿足前一位不是0方庭，且和當(dāng)前為一起組成的兩位數(shù)不大于26，則當(dāng)前dp值加上dp[i - 2], 至此可以看出來跟斐波那契數(shù)組的遞推式一樣酱固，代碼如下：
class Solution {
public:
int numDecodings(string s) {
if (s.empty()) return 0;
vector<int> dp(s.size() + 1, 0);
dp[0] = 1;
for (int i = 1; i < dp.size(); ++i) {
if (s[i - 1] != '0') dp[i] += dp[i - 1];
if (i >= 2 && s.substr(i - 2, 2) <= "26" && s.substr(i - 2, 2) >= "10") {
dp[i] += dp[i - 2];
}
}
return dp.back();
}
};
