#include<iostream>
#include <string>  
#include <vector>
using namespace std;
class Solution {
public:
    bool judg(const string& s, int idx) {
        if (idx - 1 <= 0 || s[idx - 1] >= '3' || s[idx - 1] == '0' ||
            (s[idx - 1] == '2' && s[idx] >= '7'))
            return false;

        return true;
    }
    int numDecodings(string s) {
        s = "0" + s;
        if (s[1] == '0') return 0;
        int n = s.size();
        vector<int> dp(n, 0);
        dp[0] = dp[1] = 1;
        for (int i = 2; i < n; ++i)
        {
            if (s[i] == '0')
            {
                if (judg(s, i)) dp[i] = dp[i - 2];
                else return 0;
            }
            else // s[i] > '0'
            {
                if (judg(s, i)) dp[i] = dp[i - 1] + dp[i - 2];
                else dp[i] = dp[i - 1];
            }
        }

        return dp[n - 1];
    }
};