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

91. 解码方法

程序员文章站 2022-07-16 10:22:00
...

91. 解码方法
方法一:动态规划

class Solution {
public:
    int numDecodings(string s) {
        if(s.empty() || s[0]=='0')   return 0;
        //状态:dp[i]表示以i结尾的字符串编码方法总数
        int dp[s.size()]={0};
        //初始化
        if(s.size()>0 && s[0]!='0')
            dp[0]=1;
        if(s.size()>1){
            if((s[0]=='1' && s[1]!='0') || (s[0]=='2' && s[1]>='1' && s[1]<='6'))
                dp[1]=2;
            else if(s[1]=='0' && s[0]>'2')
                return 0;
            else
                dp[1]=1;
        }
        //转移方程
        for(int i=2;i<s.size();i++){
            if(s[i]=='0'){
                if(s[i-1]=='1' || s[i-1]=='2')
                    dp[i]=dp[i-2];
                else 
                    return 0;
            }
            else if(s[i-1]=='1')
                dp[i]=dp[i-1]+dp[i-2];
            else if(s[i-1]=='2' && s[i]>='0' && s[i]<='6')
                dp[i]=dp[i-1]+dp[i-2];
            else
                dp[i]=dp[i-1];
        }
        return dp[s.size()-1];	//结果
    }
};
相关标签: leetcode