I know many people have asked about this problem before. But I can’t see what is wrong with the logic in this DP solution:
#include <cstring>
#include <iostream>
#include <math.h>
#include <string>
using namespace std;
long long int find_num_to_decode(string code, long long int digits) {
long long int num_table[digits + 1];
memset( num_table, 0, (digits + 1) * sizeof(long long int) );
num_table[0] = 0;
num_table[1] = 1;
int first_two = (code[0] - '0') * 10 + (code[1] - '0');
if (first_two >= 10 && first_two <= 26 && (code[1] - '0') != 0) {
num_table[2] = 2;
} else {
num_table[2] = 1;
}
for (int i = 2; i < digits; i++) {
int last_two = (code[i - 1] - '0') * 10 + (code[i] - '0');
if ((code[i] - '0' == 0) && (last_two < 1 || last_two > 26)) {
num_table[i + 1] = 0;
} else if (code[i] - '0' == 0) {
num_table[i + 1] = num_table[i - 1];
} else if (last_two >= 1 && last_two <= 26) {
num_table[i + 1] = num_table[i] + num_table[i - 1];
} else {
num_table[i + 1] = num_table[i];
}
}
return num_table[digits];
}
int main() {
string code;
cin >> code;
while (code != "0") {
long long int num;
num = find_num_to_decode(code, code.length());
cout << num << endl;
cin >> code;
}
}
And I am not ready to read other people’s solution yet (this is my first acode attempt). Any hints/ ideas why this is incorrect?
I have checked for:
- the provided test cases
- edge cases including 110, 1101
- invalid cases (though the forum says there isn’t a need to check for this)
Thanks a lot!