题目链接：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.

这道题的要求是判断一个只包含数字的字符串可能有几种编码方式。

动态规划，令dp[i]表示字符串的前i个字符的可能的编码方式的数量。那么递推公式如下：

  • 如果当前数字为0，则前面数字必为1或者2，否则无法进行编码转换，此时的数字0只能和前面的1或者2连在一起进行编码，因此dp[i] = dp[i-2]；
  • 如果前面数字为1或者前面数字为2且当前数字在1~6之间，说明都可以进行2种编码（分开或者和在一起），因此dp[i] = dp[i-1] + dp[i-2]；
  • 其他情况，当前数字必须单独进行编码转换，因此dp[i] = dp[i-1]。

时间复杂度：O(n)

空间复杂度：O(n)

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

class Solution
{
public:
    int numDecodings(string s)
    {
        if(s == "" || s[0] == '0')
            return 0;
            
        vector<int> dp(s.size() + 1, 0);
        dp[0] = 1, dp[1] = 1;

        for(int i = 2; i <= s.size(); ++ 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] >= '1' && s[i - 1] <= '6')
                    dp[i] = dp[i - 1] + dp[i - 2];
                else
                    dp[i] = dp[i - 1];
            }
        }
        
        return dp[s.size()];
    }
};

可以注意到，递推公式中，只是利用到了前面2个结果，因此无需申请dp数组保存前面状态，只需要2个变量a1和a2保存前面2个状态即可，这样空间复杂度降低为O(1)。

时间复杂度：O(n)

空间复杂度：O(1)

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

class Solution
{
public:
    int numDecodings(string s)
    {
        if(s == "" || s[0] == '0')
            return 0;
        
        int a1 = 1, a2 = 1, a3 = 1;
        for(int i = 1; i < s.size(); ++ i)
        {
            if(s[i] == '0')
            {
                if(s[i - 1] >= '1' && s[i - 1] <= '2')
                    a3 = a1;
                else
                    return 0;
            }
            else
            {
                if(s[i - 1] == '1' || s[i - 1] == '2' && s[i] >= '1' && s[i] <= '6')
                    a3 = a1 + a2;
                else
                    a3 = a2;
            }
            
            a1 = a2;
            a2 = a3;
        }
        
        return a3;
    }
};