[Leetcode] 91. 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.

题目大意：字母 'A'可以用1表示，B可以用2表示，以此类推，Z可以用26表示。然后给你一串数字，计算出有多少种方式可以解码成字母。比如说 12，既可以解码成A B（1 2），也可以解码成L（12）。

大致思路：由于当前s[i]转换成字母与s[i-1]有关，即当s[i-1]s[i]组成的数大于10小于27（不包括20）时，是有两种情况可以解码的。其他情况，则只能解码成1中情况，或者无法解码（比如相邻为00或者40等等）。

下面程序中：dp[i]表示s[0]到s[i-1]能解码的个数。

class Solution {
public:
    int numDecodings(string s) {
        int n=s.size();
        if(n==0) return 0;//输入为空的情况
        vector<int> dp(n+1,1);
        if(s[0]=='0') return 0;//s[0]='0'的情况
        else dp[1]=1;
        for(int i=1;i<n;i++)
        {
            if(s[i]=='0') 
            {
                if(s[i-1]<'3'&&s[i-1]>'0') dp[i+1]=dp[i-1];//出现10,20的情况
                else return 0;//出现00,30,40...的情况
            }
            else if(s[i-1]=='1'||(s[i-1]=='2'&&s[i]<'7')) dp[i+1]=dp[i]+dp[i-1];//当是s[i-1]s[i]组成的数大于10小于27时
            else dp[i+1]=dp[i];//组成的数 小于10 或者 大于26时
            
        }
        return dp[n];
    }
};

[Leetcode] 91. Decode Ways

相关推荐