Interview Questions - Counting the Number of Ways to Decode a Message
Algorithm to calculate decoding variations for a message with a given numeric scheme
Given the mapping a = 1, b = 2, ... z = 26, and an encoded message, determine the number of possible decodings. For instance, the message '121' could be decoded in 3 ways: 'aba', 'au', and 'la'. Assume all messages are valid for decoding, such as '010' being invalid.
Explanation
Base Cases:
dp[0]
is1
because there's one way to decode an empty string.dp[1]
is1
if the first character is not0
(since0
is not a valid encoding by itself).
For each position
i
in the strings
:If the current character
s[i-1]
is not0
, it means this digit can be decoded on its own, contributingdp[i-1]
ways todp[i]
.Then, if the two characters end at
i
(s[i-2, i-1]
) form a number between10
and26
, this two-digit number can be decoded together. This addsdp[i-2]
ways todp[i]
.
This approach efficiently calculates the number of ways to decode the message by building from the base cases up to the entire string, using the previously computed values to simplify the computation for each subsequent character.
function numDecodings(s) {
// Edge case for empty string
if (!s.length || s[0] === '0') return 0;
// dp array to store the number of decodings up to each point in s
const dp = Array(s.length + 1).fill(0);
// Base cases
dp[0] = 1; // There's 1 way to decode an empty string
dp[1] = 1; // There's 1 way to decode a string of length 1 (given it's not "0")
for (let i = 2; i <= s.length; i++) {
// One digit
if (s[i - 1] !== '0') {
dp[i] += dp[i - 1];
}
// Two digits
const twoDigit = parseInt(s.substring(i - 2, i), 10);
if (twoDigit >= 10 && twoDigit <= 26) {
dp[i] += dp[i - 2];
}
}
return dp[s.length];
}
console.log(numDecodings("111")); // Output: 3
Follow me on Instagram, Facebook or Twitter if you like to keep posted about tutorials, tips and experiences from my side.
You can support me from Patreon, Github Sponsors, Ko-fi or Buy me a coffee