Problem Informations

• Problem Index: 91
• Problem Link: Decode Ways
• Topics: String, Dynamic Programming

Problem Description

You have intercepted a secret message encoded as a string of numbers. The message is decoded via the following mapping:

"1" -> 'A'  
"2" -> 'B'  
...  
"25" -> 'Y'  
"26" -> 'Z'

However, while decoding the message, you realize that there are many different ways you can decode the message because some codes are contained in other codes ("2" and "5" vs "25").

For example, "11106" can be decoded into:

• "AAJF" with the grouping (1, 1, 10, 6)
• "KJF" with the grouping (11, 10, 6)
• The grouping (1, 11, 06) is invalid because "06" is not a valid code (only "6" is valid).

Note: there may be strings that are impossible to decode.

Given a string s containing only digits, return the number of ways to decode it. If the entire string cannot be decoded in any valid way, return 0.

The test cases are generated so that the answer fits in a 32-bit integer.

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 \leq s.\text{length} \leq 100$
• $s$ contains only digits and may contain leading zero(s).

Intuition

The problem of decoding a string into letters based on a given mapping can be elegantly solved using a recursive approach with memoization, also known as dynamic programming. The key intuition is to recognize that each substring of the given numeric string can either be interpreted as a single letter or, if the conditions are right, as a pair, offering multiple paths to decode the entire string. The problem resembles that of climbing stairs with multiple ways to reach the top, where each step can be viewed as decoding one or two digits. Understanding the overlapping subproblem nature of this leads us naturally to dynamic programming as a solution.

Approach

We employ a depth-first search (DFS) strategy with a dynamic programming (DP) array to count the number of ways the string can be decoded. The DP array serves as a cache to store intermediate results to prevent redundant calculations, thus optimizing the recursive approach. Here’s a detailed step-by-step breakdown of the approach:

1. Initialization: We start by initializing a DP array of the same length as the input string, $s$, with each entry set to -1. This array will be used to store the number of ways to decode the substring starting at each index. The value -1 signifies that the result for that index has not been computed yet.

2. Recursive Function dfs(s, i): This function aims to compute the number of decoding ways for the substring starting at index $i$.

   • Base Cases:
     • If the index $i$ exceeds the length of the string, return 0 as it is invalid.
     • If $i$ is at the end of the string, return 1, signifying a valid decoding path has been found.
   • Memoization Check: Before proceeding, check if the result for the current index $i$ has already been computed and stored in the DP array. If so, return that stored result to avoid recomputation.
   • Decode single or double digits:
     • If the current character at index $i$ is ‘0’, return 0, as ‘0’ cannot stand alone as a valid code.
     • Check if it’s possible to decode one character (always possible if not ‘0’) or two characters (possible if within the valid range “10” to “26”). If potential pair parsing is applicable (like “10” to “26”), proceed to compute from both the one-step and two-step ahead positions.
     • Use the recursive outcomes to populate the current DP entry.

3. Main Function numDecodings(s): This function initializes and manages the DP array and invokes the DFS function from the start of the string.

   • Clear the DP array and resize it according to the input string.
   • Begin the DFS process from index 0 and employ the recursive strategy to calculate the entire string’s decoding count.

This approach effectively breaks down the decoding problem into manageable subproblems, utilizing recursion and memoization to explore every potential decoding path and efficiently calculate the total number of valid permutations.

Code

C++

class Solution {
public:
    // Dynamic programming array to store intermediate results
    vector<int> dp;

    // Depth-first search helper function to count decoding ways
    int dfs(string& s, int i) {
        // If the index exceeds the string size, return 0 as it is invalid
        if (i > s.size()) return 0;
        
        // If the index is at the end of the string, a valid way is found
        if (i == s.size()) return 1;

        // If the result is already computed, return it to avoid recomputation
        if (dp[i] != -1) return dp[i];

        // If the current character is '0', it cannot be decoded into any letter
        if (s[i] == '0') return dp[i] = 0;

        // Check if it's possible to decode one or two characters
        if (s[i] == '1' || (i < s.size() - 1 && s[i] == '2' && s[i + 1] >= '0' && s[i + 1] <= '6')) {
            return dp[i] = dfs(s, i + 1) + dfs(s, i + 2);
        }
        else {
            return dp[i] = dfs(s, i + 1);
        }
    }

    // Main function to return the number of decoding ways
    int numDecodings(string s) {
        // Clear the dp array and resize it to match the size of the input string
        dp.clear();
        dp.resize(s.size(), -1);

        // Start the dfs from the beginning of the string
        return dfs(s, 0);
    }
};

Python

class Solution:
    # Dynamic programming array to store intermediate results
    dp = []

    # Depth-first search helper function to count decoding ways
    def dfs(self, s, i):
        # If the index exceeds the string size, return 0 as it is invalid
        if i > len(s):
            return 0
        
        # If the index is at the end of the string, a valid way is found
        if i == len(s):
            return 1

        # If the result is already computed, return it to avoid recomputation
        if self.dp[i] != -1:
            return self.dp[i]

        # If the current character is '0', it cannot be decoded into any letter
        if s[i] == '0':
            return 0

        # Check if it's possible to decode one or two characters
        if s[i] == '1' or (i < len(s) - 1 and s[i] == '2' and '0' <= s[i + 1] <= '6'):
            self.dp[i] = self.dfs(s, i + 1) + self.dfs(s, i + 2)
        else:
            self.dp[i] = self.dfs(s, i + 1)

        return self.dp[i]

    # Main function to return the number of decoding ways
    def numDecodings(self, s):
        # Clear the dp array and resize it to match the size of the input string
        self.dp = [-1] * len(s)

        # Start the dfs from the beginning of the string
        return self.dfs(s, 0)

Complexity

• Time complexity: The time complexity of the solution is $O(n)$, where $n$ is the length of the string $s$. This is because each state (represented by an index in the string) is computed at most once and stored in the dp array. The recursion involves two main cases (taking one character or two characters), but since results are cached, the computation for each index happens in constant time.

• Space complexity: The space complexity of the solution is $O(n)$, where $n$ is the length of the string $s$. This is due to the dp array used for memoization, which stores an intermediate result for each index of the string. Additionally, the recursion stack space can also go up to $O(n)$ in the worst case.