Decode Ways Leetcode Problem 91 [Python Solution]

If you’ve ever received a message encoded with a set of numbers that you need to decipher into letters, Decode Ways Leetcode Problem might interest you.

LeetCode Problem 91, “Decode Ways,” is a fascinating problem in the realm of 1-D Dynamic Programming.

It falls under the medium difficulty category and is associated with companies like Google.

In this blog post, we will delve into the problem, explore its intricacies, and provide both a brute-force and an efficient dynamic programming solution in Python.

By the end, you’ll have a comprehensive understanding of how to tackle this challenge and count the number of ways to decode a given string of digits.

Problem Overview

The problem statement begins by presenting a mapping of characters to integers:

‘A’ -> “1”
‘B’ -> “2”
…
‘Z’ -> “26”

To decode an encoded message, you must group the digits and map them back into letters using the reverse of the provided mapping.

However, there might be multiple ways to do this.

For example, the string “11106” can be mapped into “AAJF” with the grouping (1 1 10 6) or “KJF” with the grouping (11 10 6).

Notably, the grouping (1 11 06) is invalid because “06” cannot be mapped to ‘F’ since “6” is different from “06.”

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

The problem guarantees that the answer will fit within a 32-bit integer.

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 “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”).

Understanding the Constraints

Before we dive into solving the problem, it’s essential to understand the constraints given in the problem statement:

1 <= s.length <= 100: The length of the input string s can range from 1 to 100 characters.
s contains only digits and may contain leading zero(s): The string s comprises only digits (0-9) and may have leading zeros.

Leading zeros can lead to invalid encodings.

Now that we have a clear understanding of the problem and its constraints, let’s explore the solution approaches.

Brute-Force Approach

The brute-force approach involves recursively exploring all possible decoding combinations.

We start at the first character of the string and explore two possibilities:

Take the current character by itself if it’s not ‘0’.
Take the current character and the next character as a double-digit value if it’s a valid two-digit mapping (e.g., “26”).

For each of these possibilities, we move to the next character and continue the decoding process until we reach the end of the string.

If we reach the end, we have found a valid decoding and increment the count.

Python Code for Brute-Force Approach

def numDecodings(s: str) -> int:
    def dfs(i):
        if i in dp:
            return dp[i]
        if s[i] == "0":
            return 0

        res = dfs(i + 1)
        if i + 1 < len(s) and (s[i] == "1" or (s[i] == "2" and s[i + 1] in "0123456")):
            res += dfs(i + 2)
        dp[i] = res
        return res

    dp = {}
    return dfs(0)

This recursive solution uses memoization (caching) to store the results of subproblems.

It’s worth noting that this approach is not the most efficient way to solve the problem, especially for large inputs, but it helps us understand the core logic.

Efficient Approach with Dynamic Programming

To optimize the solution, we can use dynamic programming to avoid recomputing the same subproblems.

We’ll maintain an array dp to store the number of ways to decode the string up to the current position.

We iterate through the string in reverse order, calculating the number of ways to decode each substring and using the results from previous calculations to build up the solution.

The key idea is to recognize that at each position i, we can either take the current digit as a single character or combine it with the next digit (if it forms a valid two-digit mapping).

By considering both options, we can efficiently count the number of ways to decode the string.

Python Code for Efficient Approach

View on GitHub ➹

def numDecodings(s: str) -&gt; int:
    if not s or s[0] == "0":
        return 0

    n = len(s)
    dp = [0] * (n + 1)
    dp[0] = 1
    dp[1] = 1

    for i in range(2, n + 1):
        if s[i - 1] != "0":
            dp[i] += dp[i - 1]
        if "10" &lt;= s[i - 2:i] &lt;= "26":
            dp[i] += dp[i - 2]

    return dp[n]

In this dynamic programming solution, we maintain an array dp of length n + 1, where dp[i] represents the number of ways to decode the string up to the i-th position.

We initialize dp[0] and dp[1] based on the problem constraints.

We then iterate from the third position (i = 2) to the end of the string, updating dp[i] based on the two possibilities: taking the current character as a single digit or as part of a valid two-digit mapping.

This solution ensures that we don’t recompute the same subproblems and is much more efficient than the brute-force approach.

Time and Space Complexity

Let’s analyze the time and space complexity of the efficient dynamic programming solution.

Time Complexity: The time complexity of this solution is O(n), where n is the length of the input string s.

We iterate through the string once, calculating the number of ways to decode each substring.

Space Complexity: The space complexity is O(n) as well.

We use an additional array dp of length n + 1 to store the results for each position in the string.

Reasoning Behind Our Approach

The reasoning behind the efficient dynamic programming approach is based on recognizing that the number of ways to decode a string at a given position depends on the results of previous positions.

By considering the two options for each digit (single or double), we can efficiently compute the number of ways to decode the entire string.

The dynamic programming approach is more efficient than the brute-force recursive approach, as it avoids redundant calculations by storing intermediate results in the

dp array.

Conclusion

In this blog post, we tackled LeetCode Problem 91, Decode Ways We explored the problem statement, understood its constraints, and provided both a brute-force recursive solution and an efficient dynamic programming solution in Python.

By following our efficient approach, you can count the number of ways to decode a string of digits effectively.

We encourage you to comment, ask questions, make suggestions, and share this content with others who might find it helpful.

If you’d like to practice solving the problem, you can find it on LeetCode using the following link: Decode Ways – LeetCode Problem 91.

Happy coding and decoding!