91. Decode Ways

Problem Statement in English

You’re given a string s containing only digits. The string is encoded such that ‘A’ = 1, ‘B’ = 2, …, ‘Z’ = 26. You need to determine the total number of ways to decode the string.

Note that the string may contain leading zeros, and a ‘0’ cannot be decoded on its own. For example, “06” is not a valid encoding.

Approach

There is an overlapping subproblem that we can exploit here. Notice that at any index in the string, we can either treat it as a standalone digit (if it’s not ‘0’) or as part of a two-digit number (if the next digit exists and forms a valid number between 10 and 26). This leads us to a recursive solution with memoization.

If the digit is standalone, the answer is the number of ways to decode the rest of the string. If the digit can be paired with the next digit, we also add the number of ways to decode the string starting from two indices ahead.

The base cases: if we reach the end of the string, we have found a valid decoding, and if we go past the end, we return 0.

Remember to handle the case where the current digit is ‘0’, as it cannot be decoded on its own. In those cases, we should return 0.

And we’re done!

Solution in Python

class Solution:
    def numDecodings(self, s: str) -> int:
        N = len(s)

        @cache
        def dfs(i):
            if i == N:
                return 1
            elif i > N:
                return 0

            res = 0

            if i + 1 < N and s[i] != "0":
                v = int(s[i:i+2])
                if 1 <= v <= 26:
                    res += dfs(i + 2)

            if int(s[i]) > 0:
                res += dfs(i + 1)

            return res
        
        return dfs(0)

Complexity

• Time: $O(n)$
  Since we only compute answers for every index once and store them in a cache, the time complexity is linear with respect to the length of the string.

• Space: $O(n)$
  Since we are using recursion with memoization, the space complexity is also linear due to the call stack and the cache which is purely one-dimensional.

And we are done.