# [leetcode] Decode Ways

Decode Ways

A message containing letters from `A-Z` is being encoded to numbers using the following mapping:

```'A' -> 1
'B' -> 2
...
'Z' -> 26
```

Given an encoded message containing digits, determine the total number of ways to decode it.

For example,
Given encoded message `"12"`, it could be decoded as `"AB"` (1 2) or `"L"` (12).

The number of ways decoding `"12"` is 2.

```//动态规划，和上台阶那道题很类似。
//取string s的前n个字符，记f(n)为这n个字符的所有可能的decoding ways。
//如果s[n]可以被decode,（s[n]在1~9之间），f(n) = f(n - 1);
//如果s[n - 1]和s[n]组合起来可以被一起decode，且s[n]可以被decode。则f(n) = f(n - 2) + f(n - 1);
//如果s[n - 1]和s[n]组合起来可以被一起decode，但s[n]不能被decode。则f(n) = f(n - 2);
//如果上式都不满足，则返回0
class Solution {
public:
int numDecodings(string s) {
size_t len = s.size();
if(len == 0){
return 0;
}
else if(len == 1){
if(s[0] == '0'){
return 0;
}
else{
return 1;
}
}
else if(len == 2){
if(s[0] == '0' || (s[0] > '2' && s[1] == '0')){
return 0;
}
int value = (s[0] - '0') * 10 + s[1] - '0';
if(value <= 26 && s[1] != '0'){
return 2;
}
else{
return 1;
}
}
else{
int dp[len];
dp[0] = numDecodings(s.substr(0, 1));
dp[1] = numDecodings(s.substr(0, 2));
if(dp[0] == 0 || dp[1] == 0){
return 0;
}
for(int i = 2; i < len; i++){
int value = s[i] - '0';
if(value <= 9 && value >= 1){
dp[i] = dp[i - 1];
int value2 = (s[i - 1] - '0') * 10 + s[i] - '0';
if(value2 <= 26 && s[i - 1] != '0'){
//2 digits decode available
dp[i] += dp[i - 2];
}
}
else{
//digit == 0
int value2 = (s[i - 1] - '0') * 10 + s[i] - '0';
if(value2 <= 26 && s[i - 1] != '0'){
//2 digits decode available
dp[i] = dp[i - 2];
}
else{
return 0;
}
}

}
return dp[len - 1];
}

}
};```

This site uses Akismet to reduce spam. Learn how your comment data is processed.