Decode ways

code

class Solution {
public:
    int numDecodings(string s) {
        if(s.empty() || s[0] == '0')
        {
            return 0;
        }

        int n = s.length();
        vector<int> dp(n, 0);
        dp[0] = 1;
        if(n >= 2)
        {
            if(s[1] == '0' && (s[0] != '1' && s[0] != '2'))
            {
                return 0;
            }
            dp[1] = dp[0];
            int firsttwo = stoi(s.substr(0, 2));
            if(firsttwo >= 10 && firsttwo <= 26)
            {
                dp[1]++;
            }

            if(firsttwo == 10 || firsttwo == 20)
            {
                dp[1]--;
            }
        }

        for(int i = 2; i<n; i++)
        {

            if(s[i] < '0' || s[i] > '9')
            {
                return 0;
            }

            if(s[i] == '0' && (s[i-1] != '1' && s[i-1] != '2'))
            {
                return 0;
            }

            dp[i] = dp[i-1];

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

            if(nCur == 20 || nCur == 10)
            {
                dp[i] = dp[i-2];
            }
        }
        /*
        for(int i : dp)
        {
            cout<<i<<" ";
        }*/

        return dp[n-1];
    }
};

class Solution {
public:
    int numDecodings(string s) {
        if(s.empty() || s[0] == '0')
        {
            return 0;
        }

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

        for(int i = n-2; i >= 0; i--)
        {
            if(s[i] == '0')
            {
                continue;
            }
            dp[i] = stoi(s.substr(i,2)) <= 26 ? dp[i+1] + dp[i+2] : dp[i+1];
        }

        return dp[0];
    }
};