Decode ways: count letter decodings of a digit string

A message of letters was encoded as digits with A -> 1, B -> 2, …, Z -> 26, with no separators. Given the digit string, return how many different letter messages it could decode to.

Interface

Unless you agree on a different interface with the interviewer, assume:

• num_decodings(s: str) -> int — every group must be 1–26 with no leading zero, so "06" is not a valid group.

Example

num_decodings("12")     ->  2     # "AB" or "L"
num_decodings("226")    ->  3     # "BZ", "VF", "BBF"
num_decodings("06")     ->  0     # a group cannot start with 0
num_decodings("11106")  ->  2     # "AAJF" or "KJF"
num_decodings("2101")   ->  1     # only 2|10|1 = "BJA"; "01" is not a group

Constraints

• 1 <= len(s) <= 100, s holds digits only.
• The answer fits in a 32-bit integer.

Clarifying questions

• What should an empty string return?
• Can the string contain characters other than digits?
• Should I return the count only, or also the decodings?
• If the answer can be huge, should it be returned modulo some number?

What a strong answer covers

• The recurrence: ways[i] = ways[i-1] if digit i is 1–9, plus ways[i-2] if the last two digits form 10–26.
• O(n) time and O(1) space by keeping only the last two values.
• Zeros: a 0 must pair with a 1 or 2 before it, so "30" and "100" give 0.
• Why plain recursion is exponential and how memoization fixes it.
• Tests: "0", "10", "27", "101", a long run of 1s.

Follow-ups

• Return every decoding, not just the count.
• A * can stand for any digit 1–9. Count the decodings modulo 10^9 + 7.
• The mapping is a given table of codes of any length. Generalize the DP.