题目

  1. 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.

大意

用数字表示字母,给定一个数字字符串,计算有多少种字符的表示方式.

答案

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
class Solution {
public:
    bool isValid(char a,char b)
    {
        return a == '1'||(a == '2' && b <='6');
    }
    bool isValid(char a)
    {
    return a != '0';
    }
    int numDecodings(string s) 
    {
        int n = s.size();
        if(n == 0 || s[0] == '0') return 0;
        if(n == 1) return 1;
        int res = 0,fn_1 = 1,fn_2 = 1;
        for(int i = 1;i < n;i++)
        {
            int temp = fn_1;
            if(isValid(s[i])&&isValid(s[i-1],s[i]))  
              	res+=fn_1+fn_2;
            else if(!isValid(s[i])&&isValid(s[i-1],s[i])) 
              	res+=fn_2;
            else if(isValid(s[i])&&!isValid(s[i-1],s[i])) 
              	res+=fn_1;
            else if(!isValid(s[i])&&!isValid(s[i-1],s[i]))  
              	return 0;
            fn_1 = res;
            fn_2 = temp;
            res = 0;
        }
        return fn_1;
    }
};

思路

(类比爬梯子问题,是和前面两个状态有关!!!!!!)

使用动态规划,当前的dp和前两个状态有关,且有两个限制条件,第一个条件是当前遍历的字符是否为0,第二个是当前的和前一个的是否可以组成合法字符,然后四种情况分类.