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, 105].

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. 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 substring s[0:i].

  2. Base Cases:

    • dp[0] = 1 (Empty string has one way to decode - the empty way)
    • 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:i] is a valid digit (1-9), then dp[i] += dp[i-1] (We can decode this digit individually).
    • If s[i-2:i] is a valid digit (10-26), then dp[i] += dp[i-2] (We can decode these two digits together).

  4. Result: dp[n] (where n is the length of the string) will contain the total number of ways to decode the entire string.

Explanation:

The dynamic programming approach avoids redundant calculations. Instead of recursively exploring all possibilities, it builds up the solution incrementally. dp[i] is calculated based on previously computed values dp[i-1] and dp[i-2]. This significantly improves the efficiency compared to a naive recursive solution which would suffer from exponential time complexity due to overlapping subproblems.

Code:

def numDecodings(s):
    n = len(s)
    dp = [0] * (n + 1)
    dp[0] = 1  # Base case: Empty string has one way to decode

    if n > 0 and s[0] != '0':
        dp[1] = 1  # Base case: Single digit (excluding 0) has one way

    for i in range(2, n + 1):
        if s[i - 1] != '0':
            dp[i] += dp[i - 1]

        two_digit = int(s[i - 2:i])
        if 10 <= two_digit <= 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) to store the dp array. This could be optimized to O(1) by only storing the last two dp values, but the O(n) version is clearer.