#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;
}
I2luY2x1ZGUgPGlvc3RyZWFtPgp1c2luZyBuYW1lc3BhY2Ugc3RkOwoKICAgIAppbnQgbnVtRGVjb2RpbmdzKHN0cmluZyBzKSB7CiAgICBpbnQgc29sWzUwMDAwXTsKICAgIGlmIChzWzBdID09ICcwJykgewogICAgICAgIHJldHVybiAwOwogICAgfQogICAgZm9yIChpbnQgaT0wOyBpPD1zLnNpemUoKTsgaSsrKSB7CiAgICAgICAgc29sW2ldID0gMDsKICAgIH0KICAgIHNvbFswXSA9IDE7CiAgICBzb2xbMV0gPSAxOwogICAgZm9yIChpbnQgaT0yOyBpPD1zLnNpemUoKTsgaSsrKSB7CiAgICAgICAgaWYgKHNbaS0xXSAhPSAnMCcpIHsKICAgICAgICAgICAgc29sW2ldID0gc29sW2ktMV07CiAgICAgICAgfSAKICAgICAgICBpZiAoc1tpLTJdICE9ICcwJyAmJiAoKHNbaS0yXS0nMCcpKjEwICsgKHNbaS0xXS0nMCcpKSA8IDI3KSB7CiAgICAgICAgICAgICAgICBzb2xbaV0rPXNvbFtpLTJdOwogICAgICAgIH0KICAgIH0KICAgIHJldHVybiBzb2xbcy5zaXplKCldOwp9CgppbnQgbWFpbigpIHsKCXByaW50ZigiU29sdXRpb246ICVkXG4iLCBudW1EZWNvZGluZ3MoIjExMCIpKTsKCXByaW50ZigiU29sdXRpb246ICVkXG4iLCBudW1EZWNvZGluZ3MoIjAxMCIpKTsKCXByaW50ZigiU29sdXRpb246ICVkXG4iLCBudW1EZWNvZGluZ3MoIjEyNzgiKSk7CglyZXR1cm4gMDsKfQ==