leetcode - 91. 解码方法

一条包含字母 A-Z 的消息通过以下方式进行了编码：

$'A' -> 1$′A′−>1
$'B' -> 2$′B′−>2
$...$...
$'Z' -> 26$′Z′−>26

给定一个只包含数字的非空字符串，请计算解码方法的总数。

示例 1:

• 输入: “12”
• 输出: 2
• 解释: 它可以解码为 “AB”（1 2）或者 “L”（12）。

示例 2:

• 输入: “226”
• 输出: 3
• 解释: 它可以解码为 “BZ” (2 26), “VF” (22 6), 或者 “BBF” (2 2 6) 。

解题思路：使用动态规划，建立数组dp[n]，dp[i]表示以第i个字符结尾的字符串的解码方法的总数；

• 对于字符串中的某个字符$s[i](i>=2)$s[i](i>=2)，当$s[i]=='0'$s[i]==′0′时，如果$s[i-1]=='1'$s[i−1]==′1′或者$s[i]=='2'$s[i]==′2′，则有状态转移方程：$dp[i]=dp[i-2]$dp[i]=dp[i−2];

• 当$'0'<s[i]<='6'$′0′<s[i]<=′6′时，如果$s[i-1]=='1'$s[i−1]==′1′或者$s[i]=='2'$s[i]==′2′，则有状态转移方程：$dp[i]=dp[i-1]+dp[i-2]$dp[i]=dp[i−1]+dp[i−2]，否则，有状态转移方程：$dp[i]=dp[i-1]$dp[i]=dp[i−1]；

• 当$s[i]>'6'$s[i]>′6′时，如果$s[i-1]=='1''$s[i−1]==′1′′，则有状态转移方程：$dp[i]=dp[i-1]+dp[i-2]$dp[i]=dp[i−1]+dp[i−2];否则，有状态转移方程：$dp[i]=dp[i-1]$dp[i]=dp[i−1]；

因为前面使用到的状态转移方程需要dp[i-1]和dp[i-2]，所以初始化的时候需要确定$dp[0]$dp[0]和$dp[1]$dp[1]的值；

• 当$s[0]=='0'$s[0]==′0′的时候,或者$s[0]>'2'$s[0]>′2′同时$s[1]=='0'$s[1]==′0′的时候，无法解码，return 0；否则，$p[0]=1$p[0]=1；
• 当$s[0]=='2'$s[0]==′2′同时$'0'<s[1]<='6'$′0′<s[1]<=′6′，或者$dp[0]='1'同时$dp[0]=′1′同时s[i]>‘0’$时，$时， $dp[1]=2$dp[1]=2;否则，$dp[1]=1$dp[1]=1；

其C++代码如下：

class Solution {
public:
    int numDecodings(string s) {
        int length = s.size();
        vector<int> dp(length);
        if((s[0]=='0') && (s[0]-'0'>=3 && s[1]=='0'))   //判断是否能够解码
            return 0;
        if(length==1)  //如果字符串的长度是1，则直接返回1
            return 1;
        dp[0] = 1;
        if((s[0]=='2' && 0 < s[1]-'0' && s[1]-'0' <= 6) || (s[0]=='1' && 0 < s[1]-'0'))   //用于计算dp[1]的值
            dp[1] = 2;
        else
            dp[1] = 1;
        for(int i=2;i<length;i++)   //从第3个字符开始判断，使用状态转移方程
        {
            if(s[i]=='0')   //判断条件1
            {
                if(s[i-1]=='1'||s[i-1]=='2')
                    dp[i] = dp[i-2];
                else
                    return 0;
                continue;
            }
            if(s[i]!=0 && s[i]-'0'<=6)   //判断条件2
            {
                if(s[i-1]=='1'||s[i-1]=='2')
                    dp[i] = dp[i-1] + dp[i-2];
                else
                    dp[i] = dp[i-1];
                continue;
            }
            if(s[i]-'0'>6)    //判断条件3
            {
                if(s[i-1]=='1')
                    dp[i] = dp[i-1] + dp[i-2];
                else
                    dp[i] = dp[i-1];
            }
        }
        return dp[length-1];
    }
};