Decode Ways

Problem Statement

Decoding a secret message from a sequence of digits is an interesting challenge, primarily because of the varied number of ways one can interpret these digits based on predefined mappings. Each digit from '1' to '9' is mapped to a corresponding letter from 'A' to 'I', and pairs of digits from '10' to '26' map to letters from 'J' to 'Z'. However, the complexity arises in the interpretation of these mappings when digits can be combined or separated in different ways.

For instance, considering a digit string "11106", it poses multiple decoding interpretations such as:

• "AAJF" corresponding to the digit grouping (1, 1, 10, 6)
• "KJF" corresponding to the grouping (11, 10, 6)

However, not all groupings are valid due to rules such as not recognizing digits with leading zeros (e.g., 06 is invalid). Given a string s entirely composed of numbers, the task is to determine how many distinct valid ways there are to decode this string. If no valid interpretation exists due to the constraints (like presence of non-decodable sequences), the answer should be 0.

The challenge is to compute the valid ways to decode considering all potential valid and invalid groupings and differentiate cases where no valid decoding exists.

Examples

Example 1

Input:

s = "12"

Output:

2

Explanation:

"12" could be decoded as "AB" (1 2) or "L" (12).

Example 2

Input:

s = "226"

Output:

3

Explanation:

"226" could be decoded as "BZ" (2 26), "VF" (22 6), or "BBF" (2 2 6).

Example 3

Input:

s = "06"

Output:

0

Explanation:

"06" cannot be mapped to "F" because of the leading zero ("6" is different from "06"). In this case, the string is not a valid encoding, so return 0.

Constraints

• 1 <= s.length <= 100
• s contains only digits and may contain leading zero(s).

Approach and Intuition

The digit to letter mapping described can be approached using a dynamic programming method, which efficiently handles the repetitive substructure and overlaps typical in this problem. Here's a basic rundown of the proposed approach:

1. Initialize an array dp where each index i holds the number of ways to decode the string up to that position.
2. If the string starts with zero, immediately return 0 as any leading zero renders the encoding invalid.
3. Set the base case: dp[0]=1 by convention (one way to decode an empty string).
4. Iterate through the string:
   • For a single digit: Check if it's non-zero (since '0' has no corresponding letter when it stands alone) and add the number of ways to decode up to the previous character.
   • For a two-digit number formed with the current and the previous digit: Check if it lies between '10' and '26' (inclusive) to ensure that it maps to a valid letter. If valid, add to the number of ways considering the number two positions back.
5. The constraints specify handling for up to 100 characters, and since the loop runs for each character in the string, the approach sufficiently covers all possible string lengths as required.
6. Various edge cases such as strings containing non-decodable sequences are naturally handled by ensuring no addition of ways during the zero checks.

Following this method ensures that all possible valid groupings of numbers into corresponding letters are considered, and invalid paths are not counted, thereby accurately counting and returning the total number of ways to decode the message.

Solutions

class Solution {
public:
    int decodeWays(string seq) {
        if (seq[0] == '0') return 0;
    
        size_t len = seq.size();
        int previous = 1, beforePrevious = 1;
    
        for (size_t idx = 1; idx < len; idx++) {
            int count = 0;
            if (seq[idx] != '0') {
                count = beforePrevious;
            }
            int pair = stoi(seq.substr(idx - 1, 2));
            if (pair >= 10 && pair <= 26) {
                count += previous;
            }
    
            previous = beforePrevious;
            beforePrevious = count;
        }
        return beforePrevious;
    }
};