DSAPrep
Medium1-D DP

Decode Ways

A message containing letters from A-Z is encoded as digits using the mapping '1' -> 'A', '2' -> 'B', ..., '26' -> 'Z'.

Some codes are contained in other codes ('2' and '5' vs '25'), so there may be many different ways to decode a message. 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", so the string has no valid decoding.

Constraints

  • 1 <= s.length <= 100
  • s contains only digits and may contain leading zero(s).
View original on LeetCode ↗

Let dp[i] be the number of ways to decode the prefix s[0:i]. To extend a decoding of s[0:i] to s[0:i+1] (or s[0:i+2]), the last group taken off the end must be a valid code: either the single digit s[i-1] (valid if it is not '0') or the two-digit number s[i-2:i] (valid if it falls in 10..26). Summing the ways contributed by each valid last group gives the recurrence dp[i] = dp[i-1] (if s[i-1] != '0') + dp[i-2] (if s[i-2:i] is 10..26).

Top-Down Memoization

Time O(n)Space O(n)

Recurse from the front: ways(i) is the number of ways to decode the remaining suffix s[i:]. From position i, take one digit (if it is nonzero) and/or two digits (if that two-digit number is at most 26), recursing on what is left.

class Solution:
    def numDecodings(self, s: str) -> int:
        n = len(s)
        memo = {}
        def ways(i: int) -> int:
            if i == n:
                return 1
            if s[i] == '0':
                return 0
            if i in memo:
                return memo[i]
            result = ways(i + 1)
            if i + 1 < n and int(s[i:i + 2]) <= 26:
                result += ways(i + 2)
            memo[i] = result
            return result
        return ways(0)

Without memoization this branches like Fibonacci, recomputing the same suffixes repeatedly → exponential. With memoization there are only n distinct starting positions, each solved once in O(1) work beyond its (memoized) recursive calls → O(n) time. The memo dict and recursion depth cost O(n) space.

Bottom-Up DP

OptimalTime O(n)Space O(n)

Build dp[i] left to right: the number of ways to decode the prefix s[0:i]. dp[0] = 1 (the empty prefix has exactly one, trivial, decoding). Then for each i, add dp[i-1] if the last single digit s[i-1] is valid, and add dp[i-2] if the last two digits s[i-2:i] form a valid code.

class Solution:
    def numDecodings(self, s: str) -> int:
        n = len(s)
        dp = [0] * (n + 1)
        dp[0] = 1
        dp[1] = 1 if s[0] != '0' else 0
        for i in range(2, n + 1):
            if s[i - 1] != '0':
                dp[i] += dp[i - 1]
            if 10 <= int(s[i - 2:i]) <= 26:
                dp[i] += dp[i - 2]
        return dp[n]

Trace for s = "226":

1
0
·
1
·
2
·
3
1 / 4
comparingseenresult

dp[0] = 1: the empty prefix has exactly one (empty) decoding.

One pass filling n cells, O(1) work per cell → O(n) time, O(n) space for the dp array (which could be collapsed to two rolling variables for O(1) space, since each cell only needs the previous two).