Why isn't my DP solution to decode numbers and letters working for all test cases?

Question

Context
This problem was asked by dailycodingproblem and leetcode

/* Given the mapping a = 1, b = 2, ... z = 26, and an encoded message, count the number of ways it can be decoded.

For example, the message '111' would give 3, since it could be decoded as 'aaa', 'ka', and 'ak'.

You can assume that the messages are decodable. For example, '001' is not allowed. */

var AlphabetCode = function(){};
AlphabetCode.prototype.decode = function(message) {
    //dp is optimal substructure, account for zero length string such as dp[0]
    let dp = Array(1+message.length).fill(0);
    //string is of length zero
    dp[0] = 0; // no ways to decode empty (tried toggling between 0 and 1)  
    //string is of length one
    dp[1] = parseInt(message[0]) == 0 ? 0 : 1; // there is no alphabet code for 0, 'a' starts at 1 

    //string is of length two or greater
    // go up to string length inclusive because index 0 is reserved for zero string
    for (let i = 2; i <= message.length; i++){
        let singleDigit = message.substring(i-1, i);
        let doubleDigit = message.substring(i-2, i);
        //console.log(singleDigit + ' ' + doubleDigit);
        //console.log(singleDigit[0]);
        if (1 <= parseInt(singleDigit) <= 9){
            dp[i] += dp[i-1];
            //console.log(dp[i]);
        }
        //console.log(doubleDigit[0]);
        if (doubleDigit[0] !='0' && 10 <= parseInt(doubleDigit) <= 26){
            //console.log('double valid');
            dp[i] += dp[i-2];
        }
    }
    // filled out the dp array and returning the accumulation of all subproblems
    return dp[message.length];
};
combinations = new AlphabetCode();
console.log('Number of ways to decode 10 are: (expect 1) ' + combinations.decode('10'));
console.log('Number of ways to decode 12 are: (expect 2) ' + combinations.decode('12'));
console.log('Number of ways to decode 226 are: (expect 3) ' + combinations.decode('226'));
console.log('Number of ways to decode 27 are: (expect 1) ' + combinations.decode('27'));

output

Number of ways to decode 10 are: (expect 1) 1 
Number of ways to decode 12 are: (expect 2) 1
Number of ways to decode 226 are: (expect 3) 2
Number of ways to decode 27 are: (expect 1) 1

dp is the optimal substructure. Tried to change dp[0] to 0 or 1 to pass all test cases, but the outputs are not always equal to the expected number(s).

trincot · Answer 1 · 2019-07-19T20:29:37.170

Two issues:

As you already tried, but dp[0] should be 1, as really an empty string is a valid encoding of an empty message. So it counts.
You cannot do python-style double-comparisons in JavaScript, so these two conditions are both invalid:
```
if (1 <= parseInt(singleDigit) <= 9)
if (doubleDigit[0] !='0' && 10 <= parseInt(doubleDigit) <= 26)
```
change them to;
```
if (1 <= parseInt(singleDigit))
if (doubleDigit[0] !='0' && parseInt(doubleDigit) <= 26)
```
The removed "conditions" are already guaranteed to be true: a single digit cannot be greater than 9 and a double digit number will be at least 10 when you already verify that the first digit is not a zero.

Some comments on the code

Creating a constructor is overkill, as you don't maintain state in an instance of that "class". Instead create an object with a function as member.

Also, you don't need dp to have an entry for each possible string length, as you only need the "last" two results to calculate the next, so you can do with just two values.

Finally, with a ternary operator and unary plus (for conversion to number), you can calculate the next count quite succinctly:

const combinations = {
    decode(message) {
        // Only need memory of past two results (for string length - 1, and - 2)
        let dp = [1, 1];
        // No need to reject a starting zero, as the challenge says only valid input is given.
        for (let i = 2; i <= message.length; i++){
            let singleDigit = +message[i-1];
            let doubleDigit = +message.substring(i-2, i);
            dp = [
                dp[1], 
                (1 <= singleDigit) * dp[1]
                    + (10 <= doubleDigit && doubleDigit <= 26) * dp[0]
            ];
        }
        return dp[1];
    }
};

console.log('Number of ways to decode 10 are: (expect 1) ' + combinations.decode('10'));
console.log('Number of ways to decode 12 are: (expect 2) ' + combinations.decode('12'));
console.log('Number of ways to decode 226 are: (expect 3) ' + combinations.decode('226'));
console.log('Number of ways to decode 27 are: (expect 1) ' + combinations.decode('27'));

Made the changes and it works. The main issue was the double comparisons i believe — Ridhwaan Shakeel, Jul 19 '19 at 20:18
Yes. I added a few other remarks unrelated to your question. Hope they are useful. — trincot, Jul 19 '19 at 20:29
I think I understand the revisions. Is keeping the last two results generally applicable for all DP problems? — Ridhwaan Shakeel, Jul 19 '19 at 21:01

Why isn't my DP solution to decode numbers and letters working for all test cases?

1 Answers1

Some comments on the code