Decode Ways

A string consisting of uppercase english characters can be encoded to a number using the following mapping:

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

To decode a message, digits must be grouped and then mapped back into letters using the reverse of the mapping above. There may be multiple ways to decode a message. For example, "1012" can be mapped into:

• "JAB" with the grouping (10 1 2)
• "JL" with the grouping (10 12)

The grouping (1 01 2) is invalid because 01 cannot be mapped into a letter since it contains a leading zero.

Given a string s containing only digits, return the number of ways to decode it. You can assume that the answer fits in a 32-bit integer.

"12" could be decoded as "AB" (1 2) or "L" (12).

"01" cannot be decoded because "01" cannot be mapped into a letter.

Approach

Use DP where dp[i] is the number of ways to decode up to index i. A single digit contributes if it is not '0'. Two digits contribute if they form a number between 10 and 26. Keep only two previous values to save space.

Why It Works

Any decoding ending at position i is formed by either decoding one valid digit from i or a valid pair from i-1..i. Summing those possibilities yields the total. The recurrence matches the decoding rules and handles zeros correctly.

Complexity

• Time: O(n)
• Space: O(1)

Reference Implementation (Python)

class Solution:
    def numDecodings(self, s: str) -> int:
        if not s or s[0] == '0':
            return 0
        prev2, prev1 = 1, 1
        for i in range(1, len(s)):
            cur = 0
            if s[i] != '0':
                cur += prev1
            two = int(s[i - 1:i + 1])
            if 10 <= two <= 26:
                cur += prev2
            prev2, prev1 = prev1, cur
        return prev1