A message containing letters from A-Z can be encoded into numbers using the following mapping:
'A' -> "1"
"AAJF" with the grouping (1 1 10 6)
Given a string s containing only digits, return the number of ways to decode it.
The answer is guaranteed to fit in a 32-bit integer.
Example 1:
Input: s = "12"
Output: 2
Explanation: "12" could be decoded as "AB" (1 2) or "L" (12).
Example 2:
Input: s = "226"
Output: 3
Explanation: "226" could be decoded as "BZ" (2 26), "VF" (22 6), or "BBF" (2 2 6).
Example 3:
Input: s = "0"
Output: 0
Explanation: There is no character that is mapped to a number starting with 0.
The only valid mappings with 0 are 'J' -> "10" and 'T' -> "20", neither of which start with 0.
Hence, there are no valid ways to decode this since all digits need to be mapped.
Example 4:
Input: s = "06"
Output: 0
Explanation: "06" cannot be mapped to "F" because of the leading zero ("6" is different from "06").
Solution
/**
* @param {string} s
* @return {number}
* @time complexity: O(n)
* @space complexity: O(n)
*/
const numDecodings = (s) => {
return helper(s);
};
const helper = (s, i = 0, memo = {}) => {
// Reach the end when checking single digit
if (i === s.length) {
return 1;
}
// '0' is invalid
if (s.charAt(i) === '0') {
return 0;
}
// Reach the end when checking two digits
if (i === s.length - 1) {
return 1;
}
// Return previous stored results
if (memo[i] !== undefined) {
return memo[i];
}
// Check single digit
let count = helper(s, i + 1, memo);
// Check two digits
if (parseInt(s.substring(i, i + 2)) <= 26) {
count += helper(s, i + 2, memo);
}
// Save the result
memo[i] = count;
return count;
};
Test Case
const assert = require('chai').assert;
describe('Decode Ways', () => {
it('should return 2', () => {
assert.strictEqual(numDecodings('12'), 2);
});
it('should return 3', () => {
assert.strictEqual(numDecodings('226'), 3);
});
it('should return 0', () => {
assert.strictEqual(numDecodings('0'), 0);
});
it('should return 0', () => {
assert.strictEqual(numDecodings('06'), 0);
});
});
Decode Ways
✓ should return 2
✓ should return 3
✓ should return 0
✓ should return 0
4 passing (12ms)
