一条包含字母 A-Z 的消息通过以下方式进行了编码:
'A' -> 1
'B' -> 2
...
'Z' -> 26
示例:
输入: "12"
输出: 2
解释: 它可以解码为 "AB"(1 2)或者 "L"(12)。
输入: "226"
输出: 3
解释: 它可以解码为 "BZ" (2 26), "VF" (22 6), 或者 "BBF" (2 2 6) 。
题目链接: https://leetcode-cn.com/problems/decode-ways/
使用动态规划求解。
由于 dp[i] 表示前 i 个字符(s[0:i-1])的解码数,所以 dp 的长度为 n+1,最终返回 dp[n] 表示前 n 个字符的解码(str[0:n-1])。
代码如下:
class Solution {
public:
int numDecodings(string s) {
if(s[0]=='0') return 0;
int n = s.size();
vector<int> dp(n+1, 0);
dp[0] = 1; // 注意要设为 1
dp[1] = 1;
for(int i=2; i<=n; i++){
if(s[i-1]=='0'){
if(s[i-2]=='1' || s[i-2]=='2') dp[i] = dp[i-2];
else return 0;
}else{
if(s[i-2]=='1' || s[i-2]=='2'&&s[i-1]<'7') dp[i] = dp[i-1] + dp[i-2];
else dp[i] = dp[i-1];
}
}
return dp[n];
}
};