decode_1.png
decode_2.png
/**
* Abstract: A DP problem, immediately from the problem specs;
* however, state relation formulation requires careful consideration.
* To calculate dp[i], we take s[i] and proceed by checking weather s[i]
* can be decoded together with s[i - 1]. With this explaination,
* to understand the code here should not be of any difficulty.
*/
bool decode(char *s, int i) {
if (s[i - 1] == '0') return false;
int code = (s[i - 1] - '0') * 10 + (s[i] - '0');
return (code > 0 && code <= 26);
}
int numDecodings(char * s){
int n = strlen(s), dp[n];
dp[0] = s[0] == '0' ? 0 : 1;
if (n == 1) return dp[0];
if (dp[0] == 0) { return 0; }
if (s[1] == '0') {
dp[1] = decode(s, 1) ? 1 : 0;
} else {
dp[1] = decode(s, 1) ? 2 : 1;
}
if (dp[1] == 0) { return 0; }
for (int i = 2; i < n; i++) {
bool decoded = decode(s, i);
dp[i] = (s[i] == '0') ? (decoded ? dp[i - 2] : 0) : (decoded ? (dp[i - 2] + dp[i - 1]) : dp[i - 1]);
if (dp[i] == 0) { return 0; }
}
return dp[n - 1];
}
