#include <iostream>
using namespace std;

    
int numDecodings(string s) {
    int sol[50000];
    if (s[0] == '0') {
        return 0;
    }
    for (int i=0; i<=s.size(); i++) {
        sol[i] = 0;
    }
    sol[0] = 1;
    sol[1] = 1;
    for (int i=2; i<=s.size(); i++) {
        if (s[i-1] != '0') {
            sol[i] = sol[i-1];
        } 
        if (s[i-2] != '0' && ((s[i-2]-'0')*10 + (s[i-1]-'0')) < 27) {
                sol[i]+=sol[i-2];
        }
    }
    return sol[s.size()];
}

int main() {
	printf("Solution: %d\n", numDecodings("110"));
	printf("Solution: %d\n", numDecodings("010"));
	printf("Solution: %d\n", numDecodings("1278"));
	return 0;
}