Decode Ways

Given a string containing only digits, determine the total number of ways to decode it. Each digit can be mapped to a letter (e.g., '1' -> 'A', '2' -> 'B', ..., '26' -> 'Z'). This problem is a classic example of dynamic programming, where understanding overlapping subproblems and optimal substructure is key to an efficient solution.

Problem Description

You are given a string s consisting entirely of digits. Your task is to calculate the total number of ways to decode this string into letters according to the following mapping:

• '1' -> 'A'
• '2' -> 'B'
• ...
• '9' -> 'I'
• '10' -> 'J'
• '11' -> 'K'
• ...
• '26' -> 'Z'

A single digit can be decoded if it's between '1' and '9'. Two consecutive digits can be decoded together if they form a number between '10' and '26'.

Key Requirements:

1. Decode the entire string s.
2. Count all valid decoding combinations.
3. A '0' digit on its own is invalid. A '0' can only be part of a two-digit combination (e.g., '10' or '20').
4. Leading zeros in two-digit combinations are not allowed (e.g., '01' is not a valid two-digit decoding).

Expected Behavior:

The function should return an integer representing the total number of unique ways to decode the input string.

Edge Cases to Consider:

• Empty string.
• String containing only '0's.
• String containing invalid two-digit combinations (e.g., '07', '30').
• String with consecutive zeros.

Examples

Example 1:

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

Example 2:

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

Example 3:

Input: s = "0"
Output: 0
Explanation: "0" cannot be mapped to any letter.

Example 4:

Input: s = "06"
Output: 0
Explanation: "06" cannot be decoded. '0' cannot be decoded alone, and '06' is not a valid two-digit decoding.

Constraints

• 1 <= length of s <= 100
• s contains only digits.
• The output should be an integer.
• Consider potential integer overflow for very long strings if language has fixed-size integers, though for the given constraints, standard integer types should suffice.

Notes

This problem can be approached using recursion with memoization or an iterative dynamic programming solution. Think about how the number of ways to decode a substring depends on the number of ways to decode its smaller prefixes. Be mindful of how single digits and two-digit combinations contribute to the total count.