Fully Decodable Digit Message
Problem
An old pager encodes letters as numbers: A → 1, B → 2, ..., Z → 26, and concatenates them without separators. A received message s is a string of digits.
Return true if s can be split into pieces where every piece is a valid letter code (1–9, or 10–26 written with two digits). A piece can never start with 0.
Example 1
- Input:
- s = "1020"
- Output:
- true
It splits as "10" + "20" (J, T). Every 0 must be glued to the digit before it.
Example 2
- Input:
- s = "301"
- Output:
- false
The 0 cannot stand alone, and "30" is not a letter code.
Example 3
- Input:
- s = "2101"
- Output:
- true
"2" + "10" + "1".
Constraints
- 1 ≤ s.length ≤ 10^4
- s contains only digits 0–9.
Hint
Show the first hint
Think about prefixes: when can the first i digits be decoded?
Walkthrough
How to approach it
01Clarify before coding
- Is "06" a valid code for F? No: pieces never start with 0, so only 10–26 are valid two-digit codes.
- Can the string start with 0? It can appear in the input, and then the answer is false.
- Do I need the decoding itself? No, only whether one exists.
02Brute force
Recursively try cutting off one or two digits from the front and recurse on the rest.
Cost: O(2^n) without memoization: a string of 1s branches twice at every position.
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.
This problem is part of Pro.