Count Pager Message Readings

Medium1-D Dynamic Programming

Problem

Using the pager code A → 1, ..., Z → 26, a digit string s can often be read in several ways: "12" is either AB (1, 2) or L (12).

Return the number of different ways to split s into valid codes (1–9, or 10–26 with two digits; no piece may start with 0). Because the count can be huge, return it modulo 10^9 + 7. Return 0 if s cannot be read at all.

Example 1

Input:
s = "226"
Output:
3

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

Example 2

Input:
s = "1020"
Output:
1

Only "10 20".

Example 3

Input:
s = "301"
Output:
0

Constraints

  • 1 ≤ s.length ≤ 10^4
  • s contains only digits 0–9.

Hint

Show the first hint

Every reading of the first i digits ends with a one-digit or a two-digit piece.

Walkthrough

How to approach it

01Clarify before coding

  • Is "06" a code? No: two-digit codes are 10–26 only.
  • What if no reading exists? Return 0.
  • Why the modulo? A string of 10^4 ones has about 10^2090 readings; the modulo keeps numbers small.

02Brute force

Recursively cut one or two digits from the front, counting the leaves of the recursion tree.

Cost: O(φ^n) ≈ O(1.618^n): it explores every reading one by one, and there can be exponentially many.

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.