Digit Message Decodings

Medium1-D Dynamic Programming

Problem

A message of capital letters was encoded by replacing each letter with its position in the alphabet (A → 1, …, Z → 26) and joining the numbers with no separator.

Given the digit string s, return how many different letter messages could have produced it, modulo 1,000,000,007. Codes never have leading zeros, so 06 is not a valid code for F.

Example 1

Input:
s = "226"
Output:
3

2 2 6 (BBF), 22 6 (VF) and 2 26 (BZ).

Example 2

Input:
s = "06"
Output:
0

No code starts with 0.

Example 3

Input:
s = "10"
Output:
1

Only 10 (J); 1 followed by 0 is invalid.

Constraints

  • 1 ≤ s.length ≤ 100
  • s contains only digits.

Hint

Show the first hint

Like climbing stairs: the last letter consumed either one digit or two digits.

Walkthrough

How to approach it

01Clarify before coding

  • Is '0' ever a valid code on its own? No. It can only appear as the second digit of 10 or 20.
  • Can the answer be 0? Yes, e.g. '06' or '30'.
  • Why the modulo? With 100 ones the count is about 5·10^20.

02Brute force

Recursively peel one or two valid digits off the front and count the ways to finish. Memoising on the start index gives the top-down DP.

Cost: Without memo it is Fibonacci-like, O(1.62ⁿ) for strings of ones; with memo O(n) time and O(n) space.

The rest of the walkthrough is in the app

The full walkthrough (key insight, step-by-step, dry run, complexity, edge cases, pitfalls, follow-ups) and solutions in Python and JavaScript are in the app, next to an editor and a terminal that runs your code against the tests.

Solve it in the browserStart free

This problem is part of Pro.