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.

DP[i – 2]，但这种转移仅在 s[i – 2] = ‘1’ || (s[i – 2] == ‘2’ && s[i – 1] <= ‘6’)的情况下成立（因为最后一个字母Z对应的是26，所以数字不可能超过26）；另外一种是从s[i – 1]转移来，这要求s[i – 1] != ‘0’。这样就很容易写出DP[i]的转移方程，最后将DP[s.length() – 1]返回即可。

Solution:

``````
int numDecodings(char* s) {
int s_length = strlen(s);
if(s_length == 0 || s[0] == '0') return 0;
int* DP = (int*)malloc(s_length * sizeof(int));
memset(DP, 0, s_length * sizeof(int));
DP[0] = 1;

for(int i = 1; i < s_length; ++i)
{
if(s[i - 1] == '1' || (s[i - 1] == '2' && (s[i] - '0' < 7)))
{
if(i == 1) DP[i] += 1;
else DP[i] += DP[i - 2];
}

if(s[i] != '0')
DP[i] += DP[i - 1];
}
int res = DP[s_length - 1];
free(DP);
return res;
}
0ms
``````