LeetCode #91 Decode Ways

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];
}