Rob Levin
2 min readAug 13, 2019

--

I did have to add more guards then you have to meet all the test cases I have:

if (!str.length) return 0;
if (str.length === 1 && str === ‘0’)
return 0;
if (str.length === 1)
return 1;

This was to pass:

const assert = (condition, msg) => console.log(condition === true ? `Pass: ${msg}` : `Fails: ${msg}`);

assert(decode('0') === 0, 'single 0 should return 0');
assert(decode('2') === 1, 'Single digit string should return 1');

I didn’t literally copy your code as I wrote mine in JavaScript, but I don’t see how single digit char is handled and what I noticed in my version (without the guards) is that it’d proceed to the for loop which assume we have at least 2 characters to work properly.

Here’s my full JavaScript DP implementation:

  // https://leetcode.com/problems/decode-ways/
const valid = (twoDigits) => {
if (twoDigits >= 10 && twoDigits <= 26) {
return true;
}
return false;
}
const decode = (str) => {
if (!str.length) return 0;
if (str.length === 1 && str === '0') {
return 0;
}
if (str.length === 1) {
return 1;
}
// Initialize dp [1, 1, ..., 0]
const dp = [];
dp[0] = str.slice(0, 1) === '0' ? 0 : 1;
dp[1] = 1;
for (let i = 2; i <= str.length; i++) {
dp[i] = 0;
}
for (let i = 2; i <= str.length; i++) {
const singleDigit = str.slice(i-2, i-1);
if (singleDigit !== '0') {
dp[i] += dp[i - 1];
}
const twoDigits = str.slice(i-2, i);
if (valid(twoDigits)) {
dp[i] += dp[i - 2];
}
}
return dp[dp.length - 1];
};

And tests

  const assert = (condition, msg) => console.log(condition === true ? `Pass: ${msg}` : `Fails: ${msg}`);  assert(decode('0') === 0, '0 should return 0');
assert(decode('2') === 1, 'Single digit string should return 1');
assert(decode('12') === 2, '12 decodes to 1 2 and 12');
assert(decode("226") === 3, '3 digit string with single and double digits both valid returns 3');
assert(decode("227") === 2, 'returns 2 for "227 since 27 is out of range"')
assert(decode('12345') === 3, '12345 returns 3');
assert(decode('1021') === 2, '1021 returns 2');

Thanks again for this post sir—it’s been very instructive and helpful as I learn about this dynamic programming thing ;)

--

--

Responses (1)