Interview Questions — Counting the Number of Ways to Decode a Message

Photo by Daria Nepriakhina 🇺🇦 on Unsplash

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] is 1 because there's one way to decode an empty string.
• dp[1] is 1 if the first character is not 0 (since 0 is not a valid encoding by itself).

For each position i in the string s:

• If the current character s[i-1] is not 0, it means this digit can be decoded on its own, contributing dp[i-1] ways to dp[i].
• Then, if the two characters end at i (s[i-2, i-1]) form a number between 10 and 26, this two-digit number can be decoded together. This adds dp[i-2] ways to dp[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