欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

lintcode----解码方法

程序员文章站 2022-03-05 10:00:02
...

题目描述:
有一个消息包含A-Z通过以下规则编码
‘A’ -> 1
‘B’ -> 2

‘Z’ -> 26
现在给你一个加密过后的消息,问有几种解码的方式。

样例:
给你的消息为12,有两种方式解码 AB(12) 或者 L(12). 所以返回 2

标签:字符串处理、动态规划

思路讲解:

我们采用的是动态规划
我们用dp[i]表示字符串的前i个字符的解码方法,现在我们需要知道如何求得dp[i].
那么考虑加进来的第i个字符,如果i个字符可以自己构成一个信息,也就第i个不等于0,那么dp[i] = dp[i-1],如果i和i-1合在一起还能表示一个信息,那么这时,dp[i] = dp[i-2]。
所以考虑上面的情况,我们可以分析得出,当第i个字符不等于0的时候,最少dp[i] = dp[i-1],如果i和i-1还能构成一个信息,也就是在11-19到21-26之间的时候,自然dp[i] = dp[i-1]+ dp[i-2]。

详细代码:

class Solution {
public:
    /*
     * @param s: a string,  encoded message
     * @return: an integer, the number of ways decoding
     */
    int numDecodings(string &s) {
        // write your code here


        int size=s.size();
        if(size==0){
            return 0;
        }
        int *dp=new int [size];
        dp[0]=1*(s[0]!='0');

        if(size>=2){
            string t=s.substr(0,2);
            int n=atoi(t.c_str());
            dp[1]=dp[0]*(s[1]!='0')+(n>0&&n<=26);

            for(int i=2;i<size;i++)
            {
                string t=s.substr(i-1,2);
                int n=atoi(t.c_str());

                dp[i]=dp[i-1]*(s[i]!='0')+(n>=10&&n<=26)*dp[i-2];
            }
        }
        return dp[size-1];


    }
};