/**
knakul853
**/
class Solution {
public:
    int numDecodings(string s) {

        int n = s.size();
        vector<int>dp(n+1, 0);
        dp[0] = 1;
        dp[1] = s[0]=='0'?0:1;

        for(int i=2;i<=n;i++)
        {
            int  a = s[i-1]-'0';
            if(a>=1)dp[i]+= dp[i-1];

            int b = stoi(s.substr(i-2,2));
            if(b>=10 && b<=26)dp[i]+=dp[i-2];
        }

        return dp[n];

    }
};