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

LeetCode 91.解码方法 Decode Ways

程序员文章站 2022-07-05 14:22:31
...

题目链接

每个字母对应一个数字,A->1,B->2,...

给定一个字符串,只包含数字,那么,字符串有多少种解码方式?

题目其实隐藏了一个条件,像01,02,。。。这些是没有对应的字母的。如果出现00,那就直接返回0。

 

class Solution {
public:
    int numDecodings(string s) {
        int len=s.length();
        vector<int> a;//a[i]表示,字符串从0~i,有多少种译码
        if(len<=0)  return 0;
        if(s[0]=='0')   return 0;
        a.push_back(1);
        for(int i=1;i<len;i++)
        {
            int sum=0;
            int c=(s[i-1]-'0')*10+s[i]-'0';
            if(s[i]!='0')
            {
                sum+=a[i-1];
            }
            
            if(c>=10&&c<=26)
            {
                if(i-2>=0)
                    sum+=a[i-2];
                else sum+=1;
            }
            if(c==0)    return 0;
            a.push_back(sum);
        }
        return a[len-1];
    }
};