Description

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

1
2
3
4
'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.

 

Solution

可用DP解，用一个数组dp[i]存输入字符串s中从左开始直到第i个数为止有多少种解码方法，DP的规则如下：

1.若“s[i-1]s[i]”可以看成一个11到26之间的数，且s[i]自己也是一个合法的1到9之间的数，此时形成了两种解读的方案，因此dp[i]=dp[i-1]+dp[i-2]。

2.若s[i-1]大于2，那么无法在和s[i]一起构成1~26之间的数，此时只能将s[i-1]和s[i]分别看成两个数，仅有一种解读方案，因此dp[i]=dp[i-1]。

需要特别注意的点：

1.对于输入字符串中可能含有的“10”和“20”，前面的‘1’和‘2’必须连同后面的‘0’一起解读，否则就无法组成合法的字符串。

2.由于测试用例不保证输入字符串s一定合法（也即应得的解码方案数可能为0），需要对不合法的情况加以判断。根据题意不难发现，仅有数字‘0’可能造成不合法，不合法的情况有两种：

<1>“00”、“30”、“40”…“90”。（仅有“10”，“20”合法）

<2>先导的‘0’，例如s=“012345”。

 

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
#define decode(x) (s[x-1] == '1' || (s[x-1] == '2' && s[x] <= '6'))
class Solution {
public:
    int numDecodings(string s)
    {
        int len = s.length();
        if(len == 0) return 0;
        int dp[len];
        memset(dp, 0, sizeof(dp));
        /* 处理string中的'0' */
        /* 开头的'0' */
        if(s[0] == '0') return 0;
        if(s[0] > '2' && s[1] == '0') return 0;
        /* 对于每个'0'，要求它前面是'1'或'2'，否则就不合法 */
        for(int i = 0; i < len - 1; i++)
        {
            if(s[i] != '1' && s[i] != '2' && s[i + 1] == '0') return 0;
        }
        if((s[0] == '1' || s[0] == '2') && s[1] == '0')
        {
            dp[0] = 0;
            dp[1] = 1;
        }
        else
        {
            dp[0] = 1;
        }
        for(int i = 1; i < len - 1; i++)
        {
            if(dp[i]) continue;
            if((s[i] == '1' || s[i] == '2') && s[i + 1] == '0')
            {
                dp[i + 1] = dp[i] = dp[i - 1];
                i++;
                continue;
            }
            if(decode(i))
            {
                if(i > 1)
                {
                    dp[i] = dp[i - 1] + dp[i - 2];
                }
                else
                {
                    dp[i] = dp[i - 1] + 1;
                }
            }
            else
            {
                dp[i] = dp[i - 1];
            }
        }
        if(dp[len - 1] == 0)
        {
            if(decode(len - 1))
            {
                if(len > 2)
                {
                    dp[len - 1] = dp[len - 2] + dp[len - 3];
                }
                else if(len == 2)
                {
                    dp[len - 1] = dp[len - 2] + 1;
                }
            }
            else
            {
                dp[len - 1] = dp[len - 2];
            }
        }
        return dp[len - 1];
    }
};