class Solution {
public:
    int numDecodings(string s) {
        // dp
        int n = s.size();
        if(n <= 0){
            return 0;
        }
        vector<int> dp(n+1);
        dp[n] = 1; // ..... 1
        for(int i=n-1; i>=0 ; i--){
            if(s[i] == '0'){ // invalid case
                dp[i] = 0;
                continue;
            }  
            // default
            dp[i] = dp[i+1];

            // if special case
            int num = stoi(s.substr(i, 2)); // count 2
            // cout << num << endl;
            if( 10 <= num && num <= 26 ){
                dp[i] = dp[i+1] + dp[i+2];
            }
        }

        // for(int i=0; i<n+1; i++)
        //     cout << dp[i] << " ";
        return dp[0];
    }
}