Decode Ways

Problem

A message containing letters from A-Z can be encoded into numbers using the following mapping:

'A' -> 1
'B' -> 2
...
'Z' -> 26

To decode an encoded message, all the digits must be grouped then mapped back into letters using the reverse of the mapping above (there may be multiple ways). For example, "11106" can be mapped into:

• "AAJF" with the grouping (1 1 10 6)
• "KJF" with the grouping (11 10 6)

Note that the grouping (1 11 06) is invalid because "06" cannot be mapped into 'F' since "6" is different from "06".

Given a string s containing only digits, return the number of ways to decode it.

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

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").

Expected time complexity is O(n) where n is the number of characters in the given data i.e.  encoded string.

Similar Problems

[Decode Ways II](decode-ways-ii) [Decode a string to all valid interpretations](decode-a-string-to-all-valid-interpretations)

Solution

Video explanation

Here is the video explaining below methods in detail. Please check it out:

<div class="youtube-embed"><iframe src="https://www.youtube.com/embed/lRlRdOM_8bI" frameborder="0" allowfullscreen></iframe></div>

Method 1 - Recursion

To begin with, we can think of the solution for the easy cases. Suppose string is 1 letter word like: 3 . Then numDecodings = 1.

Likewise for the empty string, the numDecodings = 1 as input string would have been "" as well.

This problem is recursive and can be broken in sub-problems. We start from start of the given digit sequence. We initialize the total count of decodings as 0. We recur for two subproblems.

1. If the i-th digit is non-zero, recurse for remaining (i+1) digits and add the result to total count.
2. If the first two digits form a valid character (or smaller than 27), recur for remaining (i+2) digits and add the result to total count.

We can also start from the end of the string, following similar logic.

For e.g. for s = 226, this is how to recursion tree:

 graph TD
     A("226")
     A --> B("2")
     A --> C("22")
     
     B --> D("2")
     B --> E("26"):::green
     
     C --> F("6"):::green
     
     D --> G("6"):::green

classDef green fill:#3CB371,stroke:#000,stroke-width:1px,color:#fff; 

Code

Java

class Solution {
    public int numDecodings(String s) {
        return dfs(s, 0);
    }
    
    // Recursive helper function
    private int dfs(String s, int idx) {
        // If we've processed all characters in the string, it's a valid decoding
        if (idx == s.length()) {
            return 1;
        }
        
        // If the current character is '0', it's invalid
        if (s.charAt(idx) == '0') {
            return 0;
        }
        
        // Decode one-digit
        int ans = dfs(s, idx + 1);
        
        // Decode two-digits only if within valid range '10' to '26'
        if (idx < s.length() - 1) {
            int twoDigit = Integer.parseInt(s.substring(idx, idx + 2));
            if (twoDigit >= 10 && twoDigit <= 26) {
                ans += dfs(s, idx + 2);
            }
        }
        
        return ans;
    }
}

Python

class Solution:
    def numDecodings(self, s: str) -> int:
        def dfs(idx: int) -> int:
            # If we've processed all characters in the string, it's a valid decoding
            if idx == len(s):
                return 1
            
            # If the current character is '0', it's invalid
            if s[idx] == '0':
                return 0
            
            # Decode one-digit
            ans: int = dfs(idx + 1)
            
            # Decode two-digits only if within valid range '10' to '26'
            if idx < len(s) - 1:
                two_digit: int = int(s[idx:idx + 2])
                if 10 <= two_digit <= 26:
                    ans += dfs(idx + 2)
            
            return ans
        
        # Start recursion from index 0
        return dfs(0)

Complexity

• ⏰ Time complexity: O(2^n), as we are making 2 decisions at each point and depth of this tree will be proportional to n.
• 🧺 Space complexity: O(n) coming from the depth of the recursion.

Dry Run

Here we are going from left to right.

numWays("12345") = "A" + numWays("2345") and "L" + numWays("345")

In the above logic, we have not handled the case when data starts with 0. eg.

numWays("011") = 0

To do so, we can do following:

if(digits[idx] == ‘0'){
    return 0;
}

Now, handle when we get numWays as negative and return the value accordingly.

The time complexity of above the code is exponential. If we take a closer look at the above program, we can observe that the recursive solution is similar to [Generate Nth Fibonacci Number](generate-nth-fibonacci-number).

Method 2 - Top Down DP with Memoization OR DFS with Cache

Now, let’s see how we can make the process more efficient. When decoding a substring, we notice that there is repetitive work being performed. For example, in the recursion tree for a small string like 226, the digit 6 is decoded multiple times across different recursive paths.

To optimise this, we can observe that if we are at a certain index in the string, the number of ways to decode the substring from that index to the end will always remain the same, regardless of the path taken to reach that index. This opens up opportunities for memoisation or caching.

Using memoisation, we store the results of previously computed subproblems in a cache (e.g., a dictionary in Python or a HashMap in Java). Whenever a substring starting at a specific index is encountered again, we can simply retrieve the cached result instead of recalculating it.

This optimisation reduces the time complexity to O(n) because we now process each index in the string only once. The space complexity remains O(n) due to two factors:

1. The recursion stack depth (proportional to the length of the string).
2. The memoisation table used to store intermediate results.

Code

Java

class Solution {
    public int numDecodings(String s) {
        // Memoisation map to store results for each index
        Map<Integer, Integer> memo = new HashMap<>();
        return dfs(s, 0, memo);
    }
    
    private int dfs(String s, int idx, Map<Integer, Integer> memo) {
        // If we've processed all characters, it's a valid decoding
        if (idx == s.length()) {
            return 1;
        }
        
        // If the current character is '0', it's invalid
        if (s.charAt(idx) == '0') {
            return 0;
        }
        
        // Check the memoisation cache
        if (memo.containsKey(idx)) {
            return memo.get(idx);
        }
        
        // Decode one-digit
        int ans = dfs(s, idx + 1, memo);
        
        // Decode two-digits, only if within valid range '10' to '26'
        if (idx < s.length() - 1) {
            int twoDigit = Integer.parseInt(s.substring(idx, idx + 2));
            if (twoDigit >= 10 && twoDigit <= 26) {
                ans += dfs(s, idx + 2, memo);
            }
        }
        
        // Save the result in the memoisation map
        memo.put(idx, ans);
        return ans;
    }
}

Python

class Solution:
    def numDecodings(self, s: str) -> int:
        # Memoisation dictionary to store results for each index
        memo: dict[int, int] = {}
        
        def dfs(idx: int) -> int:
            # If we've processed all characters, it's a valid decoding
            if idx == len(s):
                return 1
            
            # If the current character is '0', it's invalid
            if s[idx] == '0':
                return 0
            
            # Check the memoisation cache
            if idx in memo:
                return memo[idx]
            
            # Decode one-digit
            ans: int = dfs(idx + 1)
            
            # Decode two-digits, only if within valid range '10' to '26'
            if idx < len(s) - 1:
                two_digit: int = int(s[idx:idx + 2])
                if 10 <= two_digit <= 26:
                    ans += dfs(idx + 2)
            
            # Save the result in the memoisation dictionary
            memo[idx] = ans
            return ans
        
        # Begin recursion from index 0
        return dfs(0)

Complexity

• ⏰ Time complexity: O(n). As, we are now caching the value now, we don't have to go into 2^n paths.
• 🧺 Space complexity: O(n)

Method 3 - Bottom up DP

We can also solve this problem iteratively using a bottom-up DP approach by solving for smaller substrings first and gradually building up the solution for the full string. This eliminates any recursion overhead.

1. Similar to the caching mechanism used in the previous approach, we initialise a DP table, where each entry dp[i] represents the number of ways to decode the substring s[0:i] (i.e., the first i characters of the string).

Base Cases

Before filling the DP table, let's set up the base cases:

• dp[0] = 1: There is one way to decode an empty string — by doing nothing.
• For the first character:
  • If it's '0', dp[1] = 0, as no valid decoding is possible for a single 0.
  • Otherwise, dp[1] = 1 because a valid single-digit mapping exists (e.g., '1' -> A).
• Remaining dp values are initialised to 0.

Filling the DP Table

After setting the base cases, we iterate through the DP table from dp[2] to dp[n] (where n = len(s)) and calculate the result for each position using previously computed results:

1. At each position i, consider the following two possibilities:
   • Single-digit decoding:
     • If the current character s[i-1] is not '0', it can be decoded, and we add dp[i-1] to dp[i].
     • This means the current character (e.g., "6") maps to a valid letter from the previous position.
   • Two-digit decoding:
     • If the last two characters s[i-2:i] form a number between 10 and 26, they can be decoded as a valid letter, and we add dp[i-2] to dp[i].
     • This accounts for valid combined mappings (e.g., "22" -> V).

Code

Java

class Solution {
    public int numDecodings(String s) {
        int n = s.length();
        if (n == 0 || s.charAt(0) == '0') {
	        return 0;
	    }

        // DP array to store decoding counts
        int[] dp = new int[n + 1];
        dp[0] = 1; // There is one way to decode an empty string
        dp[1] = s.charAt(0) != '0' ? 1 : 0; // Check if the first character is valid
        
        for (int i = 2; i <= n; i++) {
            // Single-digit decoding
            if (s.charAt(i - 1) != '0') {
                dp[i] += dp[i - 1];
            }
            
            // Two-digit decoding
            int twoDigit = Integer.parseInt(s.substring(i - 2, i));
            if (twoDigit >= 10 && twoDigit <= 26) {
                dp[i] += dp[i - 2];
            }
        }
        
        return dp[n]; // Total ways to decode the entire string
    }
}

Python

class Solution:
    def numDecodings(self, s: str) -> int:
        n = len(s)
        if n == 0 or s[0] == '0':
            return 0

        # DP array to store decoding counts
        dp = [0] * (n + 1)
        dp[0] = 1  # There is one way to decode an empty string
        dp[1] = 1 if s[0] != '0' else 0  # Check if the first character is valid

        for i in range(2, n + 1):
            # Single-digit decoding
            if s[i - 1] != '0':
                dp[i] += dp[i - 1]
            
            # Two-digit decoding
            two_digit = int(s[i - 2:i])
            if 10 <= two_digit <= 26:
                dp[i] += dp[i - 2]
        
        return dp[n]  # Total ways to decode the entire string

Complexity

• ⏰ Time complexity: O(n)
• 🧺 Space complexity: O(n)

Method 4 - Space-optimized Bottom-up DP

If we examine the Bottom-Up DP Approach, we notice that dp[i] for position i depends only on the previous two entries: dp[i-1] (for single-digit decoding) and dp[i-2] (for two-digit decoding). This means we do not need to maintain the entire DP table. Instead, we can use two variables to store the results of the last two computations (dp[i-1] and dp[i-2]).

This recurrence is conceptually similar to the Fibonacci sequence, except that here the summation is conditional and depends on whether the current single-digit or two-digit substring forms a valid mapping.

Here is the logic:

1. Use two variables (prev2 and prev1) and a temporary variable (current):
   • prev2: Represents dp[i-2], which is the decoding count for the substring up to two positions prior.
   • prev1: Represents dp[i-1], which is the decoding count for the substring up to the previous position.
   • current: Temporarily stores the decoding count for the current position i.
2. Set up the base cases:
   • Initialise prev2 = 1 because there is exactly one way to decode an empty string (doing nothing).
   • Check if the first character of the string is valid:
     • If the first character is not '0', set prev1 = 1 as it can be decoded alone. Otherwise, set prev1 = 0.
3. Iterate from index 2 to n (where n is the length of the string), updating the decoding count:
   • Single-digit decoding:
     • If the character s[i-1] (current character) is not '0', it can be decoded as a letter.
     • Add prev1 (the decoding count of the string ending at i-1) to current.
   • Two-digit decoding:
     • If the last two characters (s[i-2:i]) form a valid number between 10 and 26, they can be decoded together.
     • Add prev2 (the decoding count of the string ending at i-2) to current.
4. At each iteration, update prev2 and prev1:
   • Move the window forward by setting prev2 = prev1 and prev1 = current.
5. At the end of the loop, prev1 contains the total decoding ways for the entire string.

Code

Java

class Solution {
    public int numDecodings(String s) {
        int n = s.length();
        if (n == 0 || s.charAt(0) == '0') {
	        return 0;
	    }

        // Initialise prev2 and prev1 for base cases
        int prev2 = 1; // dp[0]
        int prev1 = s.charAt(0) != '0' ? 1 : 0; // dp[1]

        for (int i = 2; i <= n; i++) {
            int current = 0;

            // Single-digit decoding
            if (s.charAt(i - 1) != '0') {
                current += prev1;
            }

            // Two-digit decoding
            int twoDigit = Integer.parseInt(s.substring(i - 2, i));
            if (twoDigit >= 10 && twoDigit <= 26) {
                current += prev2;
            }

            // Update prev2 and prev1 for the next iteration
            prev2 = prev1;
            prev1 = current;
        }

        return prev1; // Final result
    }
}

Python

class Solution:
    def numDecodings(self, s: str) -> int:
        n = len(s)
        if n == 0 or s[0] == '0':
            return 0

        # Initialise prev2 and prev1 for base cases
        prev2 = 1  # dp[0]
        prev1 = 1 if s[0] != '0' else 0  # dp[1]

        for i in range(2, n + 1):
            current = 0

            # Single-digit decoding
            if s[i - 1] != '0':
                current += prev1

            # Two-digit decoding
            two_digit = int(s[i - 2:i])
            if 10 <= two_digit <= 26:
                current += prev2

            # Update prev2 and prev1 for the next iteration
            prev2, prev1 = prev1, current

        return prev1  # Final result

Complexity

• ⏰ Time complexity: O(n), as we process every character of the string exactly once.
• 🧺 Space complexity: O(1), as we no longer store the entire DP table, but only the last two results (prev1 and prev2).