Decode Ways

Problem

A message containing letters from A-Z can be encoded into numbers. Given a string s containing only digits, return the number of ways to decode it.

Examples

The brute-force approach

Recursively try taking 1 digit or 2 digits at a time. If 1 digit is not '0', recurse on the rest. If 2 digits form a valid code (10-26), also recurse on the rest. Sum both results.

def decode(i):
    if i == len(s): return 1  # successfully decoded
    if s[i] == '0': return 0  # can't decode leading zero
    result = decode(i + 1)    # take one digit
    if i + 1 < len(s):
        two = int(s[i:i+2])
        if 10 <= two <= 26:
            result += decode(i + 2)  # take two digits
    return result
return decode(0)

O(2^n) calls without memoization — the same suffixes are computed repeatedly.

Spotting the pattern

This is a Dynamic Programming problem. The key question to ask yourself:

If dp[i] depends on dp[i+1] and dp[i+2], and you know dp[n]=1, dp[n+1]=0, which direction should you fill the dp array?

Answering that is where it clicks, and it's exactly what the guided walkthrough below builds with you: the pattern reasoning, a progressive hint ladder that never spoils the answer, a row-by-row dry run, the optimized solution, and an in-browser editor to run your code against real test cases.