Code Implementation

class Solution:
    def numDecodings(self, s: str) -> int:
        if not s or s[0] == '0':
            return 0
        n = len(s)
        dp = [0] * (n + 1)
        dp[0] = 1
        dp[1] = 1
        for i in range(2, n + 1):
            if s[i-1] != '0':
                dp[i] += dp[i-1]
            if 10 <= int(s[i-2:i]) <= 26:
                dp[i] += dp[i-2]
        return dp[n]
      

class Solution {
public:
    int numDecodings(string s) {
        if (s.empty() || s[0] == '0') return 0;
        int n = s.size();
        vector<int> dp(n + 1, 0);
        dp[0] = 1;
        dp[1] = 1;
        for (int i = 2; i <= n; ++i) {
            if (s[i-1] != '0')
                dp[i] += dp[i-1];
            int two = stoi(s.substr(i-2, 2));
            if (two >= 10 && two <= 26)
                dp[i] += dp[i-2];
        }
        return dp[n];
    }
};
      

class Solution {
    public int numDecodings(String s) {
        if (s == null || s.length() == 0 || s.charAt(0) == '0') return 0;
        int n = s.length();
        int[] dp = new int[n + 1];
        dp[0] = 1;
        dp[1] = 1;
        for (int i = 2; i <= n; i++) {
            if (s.charAt(i-1) != '0') dp[i] += dp[i-1];
            int two = Integer.parseInt(s.substring(i-2, i));
            if (two >= 10 && two <= 26) dp[i] += dp[i-2];
        }
        return dp[n];
    }
}
      

var numDecodings = function(s) {
    if (!s || s[0] === '0') return 0;
    let n = s.length;
    let dp = new Array(n + 1).fill(0);
    dp[0] = 1;
    dp[1] = 1;
    for (let i = 2; i <= n; i++) {
        if (s[i-1] !== '0') dp[i] += dp[i-1];
        let two = Number(s.substring(i-2, i));
        if (two >= 10 && two <= 26) dp[i] += dp[i-2];
    }
    return dp[n];
};
      

Problem Description

You are given a string s containing only digits, which represents an encoded message. Each letter maps to a number as follows: 'A' -> "1", 'B' -> "2", ..., 'Z' -> "26". Your task is to determine how many different ways the string s can be decoded into letters.

Constraints:

• The input string s consists only of digits and may not start with '0'.
• '0' cannot be mapped to any letter directly, but "10" and "20" are valid mappings.
• Each digit or pair of digits must be mapped to a letter, and you cannot reuse or skip digits.
• Return the total number of valid decodings for s.

Thought Process

At first glance, this problem seems similar to counting the number of ways to climb stairs, as each position in the string can be reached either by taking one step (decoding a single digit) or two steps (decoding a pair of digits). However, there are constraints: not every single or double digit forms a valid letter. For example, '0' alone is not valid, and numbers above 26 do not correspond to any letter.

A brute-force approach would be to try every possible way to split the string into valid single or double digits, recursively checking all combinations. However, this leads to repeated calculations and exponential time complexity.

To optimize, we observe that the number of ways to decode up to a certain position depends only on the previous two positions, much like the Fibonacci sequence. This insight suggests using dynamic programming to store intermediate results and avoid redundant computation.

Solution Approach

We use dynamic programming to solve the problem efficiently. Here’s how we build the solution step-by-step:

1. Define State: Let dp[i] represent the number of ways to decode the substring s[0:i] (the first i characters).
2. Initialization:
   • dp[0] = 1: There is one way to decode an empty string.
   • dp[1] = 1 if s[0] is not '0', otherwise 0.
3. Transition:
   • For each position i from 2 to n (length of s):
   • If s[i-1] (the current character) is not '0', add dp[i-1] to dp[i] (single digit decode).
   • If the substring s[i-2:i] forms a valid two-digit number (between 10 and 26), add dp[i-2] to dp[i] (double digit decode).
4. Result: dp[n] will hold the total number of ways to decode the entire string.

We use an array (or variables) to store results for each subproblem, ensuring each state is computed only once. This reduces the time complexity from exponential to linear.

Example Walkthrough

Let's take s = "226" as an example. We want to find out how many ways this can be decoded.

• Initialization: dp[0] = 1, dp[1] = 1 (since '2' is valid).
• i = 2 (substring: "22"):
  • s[1] = '2' is not '0', so dp[2] += dp[1] = 1.
  • s[0:2] = "22" is between 10 and 26, so dp[2] += dp[0] = 1.
  • Now dp[2] = 2.
• i = 3 (substring: "226"):
  • s[2] = '6' is not '0', so dp[3] += dp[2] = 2.
  • s[1:3] = "26" is between 10 and 26, so dp[3] += dp[1] = 1.
  • Now dp[3] = 3.

The three ways to decode "226" are: "2 2 6" ("BBF"), "22 6" ("VF"), and "2 26" ("BZ").

Time and Space Complexity

Brute-force (recursive): For each position, we try one or two digit splits, leading to O(2ⁿ) time complexity, where n is the length of the string. This is highly inefficient for large inputs.

Optimized Dynamic Programming:

• Time Complexity: O(n) because we iterate through the string once, computing each state in constant time.
• Space Complexity: O(n) for the DP array. If we only keep the last two results, we can reduce this to O(1).

Summary

We approached the "Decode Ways" problem by recognizing its similarity to the Fibonacci sequence and leveraging dynamic programming for an efficient solution. By breaking the problem into subproblems and storing their results, we avoid redundant calculations and ensure a linear-time solution. The key insight is to check for valid single and double digit mappings at each step, updating our count accordingly. This approach is both elegant and robust, handling all edge cases with minimal code.