Medium

Decode Ways

LAB

Return the number of ways to decode a digit string where A=1 through Z=26.

EXAMPLES

Example 1

Input
{
  "s": "12"
}

Output
2

FUNCTION SHAPE

s: string→int

SOLUTION NOTE

At each position, try decoding one digit (if not '0') or two digits (if forms valid number 10-26). Sum the ways.

Reveal reference solution +

pythonREFERENCE

def numDecodings(self, s: str) -> int:
    @cache
    def dp(i):
        if i >= len(s): return 1
        if s[i] == '0': return 0

        # Take one digit
        res = dp(i + 1)

        # Take two digits if valid (10-26)
        if i + 1 < len(s) and 10 <= int(s[i:i+2]) <= 26:
            res += dp(i + 2)

        return res

    return dp(0)

TimeO(n)

SpaceO(n)

Open on LeetCode ↗