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 s containing only digits, determine the total number of ways to decode it.

The test cases are generated so 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 to Solve

1. Dynamic Programming Approach: We'll use dynamic programming to solve this problem efficiently. We create a DP array dp where dp[i] represents the number of ways to decode the string up to index i.

2. Base Cases:

   • dp[0] = 1 (empty string has one way to decode)
   • dp[1] = 1 if s[0] is a valid digit (1-9), otherwise 0.

3. Iteration: We iterate through the string from index 2. For each index i:

   • If s[i-1] and s[i] form a valid number (between 10 and 26), then dp[i] += dp[i-2].
   • If s[i] is a valid digit (1-9), then dp[i] += dp[i-1].

4. Return: The final answer is dp[n], where n is the length of the string.

Explanation

The dynamic programming approach avoids redundant calculations. dp[i] leverages the previously computed values dp[i-1] and dp[i-2] to efficiently determine the number of ways to decode up to index i. We only need to consider the current digit and the previous digit to determine the number of decoding possibilities.

Code

public class Solution {
    public int NumDecodings(string s) {
        int n = s.Length;
        if (n == 0) return 0;

        int[] dp = new int[n + 1];
        dp[0] = 1; // Base case: empty string has one way to decode

        if (s[0] != '0') { // Base case: first digit
            dp[1] = 1;
        }


        for (int i = 2; i <= n; i++) {
            int currentDigit = s[i - 1] - '0';
            int prevDigit = s[i - 2] - '0';

            // Check if two-digit combination is valid (10-26)
            if (prevDigit == 1 || (prevDigit == 2 && currentDigit <= 6)) {
                dp[i] += dp[i - 2];
            }

            // Check if single digit is valid (1-9)
            if (currentDigit >= 1 && currentDigit <= 9) {
                dp[i] += dp[i - 1];
            }
        }

        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 using only three variables to store the necessary DP values instead of the entire array.