91. Decode Ways - Detailed Explanation

Problem Statement

Given a non-empty string containing only digits, determine the total number of ways to decode it. The decoding follows the mapping where "1" maps to "A", "2" maps to "B", …, "26" maps to "Z". For example, the string "12" can be decoded as "AB" (1, 2) or "L" (12). The challenge is to count all valid decodings of the string.

Examples

Example 1

Input:

"12"

Output:

2

Explanation:
There are two ways to decode "12":

1. "1" and "2" -> "A" "B"
2. "12" -> "L"

Example 2

Input:

"226"

Output:

3

Explanation:
There are three ways to decode "226":

1. "2", "2", "6" -> "B", "B", "F"
2. "22", "6" -> "V", "F"
3. "2", "26" -> "B", "Z"

Example 3

Input:

"06"

Output:

0

Explanation:
"0" cannot be decoded on its own and "06" is not valid, so there are no valid decodings.

Constraints

• The input string consists only of digits and is non-empty.
• The string may have leading zeros or zeros in the middle, which have special handling because "0" cannot map to any letter on its own.
• The length of the string can be large, so an efficient solution is required.

Hints

1. Dynamic Programming Insight:
   Think of the problem as counting the number of ways to partition the string into valid chunks. A digit can be decoded by itself if it is not "0", and two consecutive digits can be decoded together if they form a number between 10 and 26.

2. State Definition:
   Define a state dp[i] as the number of ways to decode the substring starting at index i. The final answer will be dp[0].

3. Transition:

   • If the digit at position i is not "0", then you can decode it on its own, which contributes dp[i+1] ways.
   • If the two digits starting at position i form a valid number (between 10 and 26), then they contribute dp[i+2] ways.

4. Base Cases:

   • dp[n] = 1, where n is the length of the string (an empty string has one valid decoding).
   • Handle cases where the string starts with "0", which immediately yields 0 ways.

Approach: Dynamic Programming

The dynamic programming (DP) approach builds the solution from the end of the string towards the beginning.

1. Initialization:
   Create an array dp of size n + 1, where n is the length of the string. Set dp[n] = 1 because an empty substring has one valid decoding.

2. Iterative Transition:
   Iterate from the second last character to the first character:

   • If the current character is "0", then dp[i] = 0 because "0" cannot be decoded.
   • Otherwise, set dp[i] to dp[i+1] (decoding the current digit on its own).
   • Then, if the substring from i to i+1 (two characters) forms a valid number between 10 and 26, add dp[i+2] to dp[i].

3. Result:
   After filling the DP array, dp[0] will hold the total number of ways to decode the entire string.

Step-by-Step Walkthrough

Consider the string "226":

• Initialize dp with size 4 (since length is 3):
  dp[3] = 1 (base case).

• Start from index 2 ("6"):

  • "6" is valid on its own → dp[2] = dp[3] = 1.

• Move to index 1 ("2" in "26"):

  • "2" is valid → start with dp[1] = dp[2] = 1.
  • Check two-digit number "26": it is valid (10 ≤ 26 ≤ 26) → add dp[3] → dp[1] = 1 + 1 = 2.

• Move to index 0 ("2" in "226"):

  • "2" is valid → dp[0] = dp[1] = 2.
  • Check two-digit number "22": it is valid → add dp[2] → dp[0] = 2 + 1 = 3.

Thus, the final answer is dp[0] = 3.

Python Code