Decode Ways medium

Problem Statement

A message containing letters from A-Z is being encoded to numbers using the following mapping:

'A' -> 1 'B' -> 2 ... 'Z' -> 26

Given a non-empty string containing only digits, determine the total number of ways to decode it.

The test cases are generated such that the answer fits in the range [1, 10⁵].

Example 1:

Input: s = "12" Output: 2 Explanation: It could be decoded as "AB" (1 2) or "L" (12).

Example 2:

Input: s = "226" Output: 3 Explanation: It could be decoded as "BZ" (2 26), "VF" (22 6), or "BBF" (2 2 6).

Steps

1. Base Cases: If the string is empty or starts with '0', there are no valid decodings. If the string has length 1, there's only one decoding.

2. Dynamic Programming: We use dynamic programming to build up a solution. Create a DP array dp where dp[i] represents the number of ways to decode the substring s[0...i].

3. Iteration: Iterate through the string. For each position i:

   • If s[i] is not '0', we can add the number of ways to decode the substring up to i-1 (dp[i-1]). This represents decoding the current digit individually.
   • If s[i-1] and s[i] form a number between 10 and 26 (inclusive), we can add the number of ways to decode the substring up to i-2 (dp[i-2]). This represents decoding the last two digits as a single letter.

4. Result: The final result is dp[n-1], where n is the length of the string.

Explanation

The dynamic programming approach avoids redundant calculations. Instead of recursively exploring all possibilities, we build up the solution iteratively. Each dp[i] depends only on dp[i-1] and dp[i-2], ensuring efficiency.

Code

function numDecodings(s: string): number {
    const n = s.length;
    if (n === 0 || s[0] === '0') return 0; // Base case: empty or starts with '0'

    const dp: number[] = new Array(n + 1).fill(0);
    dp[0] = 1; // Empty substring has one way to decode
    dp[1] = 1; // Single digit has one way to decode

    for (let i = 2; i <= n; i++) {
        const currentDigit = parseInt(s[i - 1]);
        const twoDigitNum = parseInt(s.substring(i - 2, i));

        if (currentDigit >= 1) {
            dp[i] += dp[i - 1];
        }
        if (twoDigitNum >= 10 && twoDigitNum <= 26) {
            dp[i] += dp[i - 2];
        }
    }
    return dp[n];
}

Complexity

• Time Complexity: O(n), where n is the length of the string. We iterate through the string once.
• Space Complexity: O(n), due to the dp array. This could be optimized to O(1) by only storing the last two DP values.