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来解决,对于字符串中每一个数字s[i],有两种情况0和非0。如果是0,则只能从s[i – 2]转移得到,也就是说DP[i] = DP[i – 2]。如果不是0则有两种方式转移到DP[i],一种是从

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

Leave a Reply

Your email address will not be published. Required fields are marked *