Decode Ways in TypeScript: Give Zero Its Proper Job

12 can mean one letter or two. 10 can only mean one. 30 cannot mean anything in this encoding, despite looking perfectly respectable as a number. Decode Ways is a small counting problem whose awkward cases are all hiding in plain sight.
In LeetCode's problem, the strings 1 through 26 represent letters. We are given a digit string and asked how many complete decodings it has. We don't need to build the decoded messages, and converting the whole input to a number would lose information we need, particularly leading zeroes.
My Word Break walkthrough asks whether a string can be segmented successfully. Here, the possible pieces are fixed and short, but the question is a count. Remembering that distinction saves us from returning one merely because we have found the first valid route.
Count Complete Decodings of a Prefix
I define ways[i] as the number of valid decodings of the first i digits. This includes an empty prefix, ways[0] = 1. There is one way to have decoded nothing: choose no pieces. That value gives the first valid piece something to extend.
This isn't a claim that an empty message is part of the challenge input. The input is non‑empty. The empty prefix is an internal starting state, much like the starting square in a path‑counting problem.
To calculate the next value, classify decodings by their final piece. It has either one digit or two, so there are only two cases to inspect:
- If the final digit is
1through9, append that one‑digit letter to every decoding of the previous prefix. - If the final two digits form a value from
10through26, append that two‑digit letter to every decoding of the prefix before them.
These groups cannot overlap. A particular decoding cannot end with both a one‑digit piece and a two‑digit piece. We can therefore add their counts without counting the same decoding twice.
Zero Stops One Route, Not Necessarily Both
A zero cannot stand alone. It can be the second digit of 10 or 20, and those pairs are valid. This is why rejecting any string containing zero is wrong, and why accepting any pair whose numerical value is at most 26 is also wrong. 06 is not a second spelling of 6.
For 2101, the prefix counts show exactly what survives:
| Prefix | One‑digit contribution | Two‑digit contribution | Total |
|---|---|---|---|
| Empty | Starting state | Starting state | 1 |
| 2 | 1 | 0 | 1 |
| 21 | 1 | 1 | 2 |
| 210 | 0 | 1 | 1 |
| 2101 | 1 | 0 | 1 |
At 210, the zero removes the one‑digit option. The pair 10 can extend the decoding of 2, leaving one route. The final 1 extends that route, whilst 01 contributes nothing. The complete grouping is 2, 10, 1.
Notice that a count can go down when a new digit arrives. We are counting decodings of the entire current prefix, not collecting every successful fragment we have ever seen. Once a fragment can no longer extend, it stops contributing.
Write the Two Cases Directly
I use a table first so that each prefix count remains available to inspect.
const numDecodings = (digits: string): number => {
const ways = Array<bigint>(digits.length + 1).fill(0n);
ways[0] = 1n;
for (let length = 1; length <= digits.length; length += 1) {
if (digits[length - 1] !== '0') ways[length] += ways[length - 1];
if (length >= 2) {
const pair = digits.slice(length - 2, length);
if (pair >= '10' && pair <= '26') ways[length] += ways[length - 2];
}
}
return Number(ways[digits.length]);
};The pair comparison is between two strings of exactly two decimal digits. Lexicographic order therefore agrees with numeric order here. The lower bound excludes leading‑zero pairs, and the upper bound excludes 27 onwards. That reasoning depends on the problem's digit‑only input; it isn't a general string‑to‑number validation routine.
I have used bigint for the internal counts, then converted the final answer to number. LeetCode guarantees that final answer fits a signed 32‑bit integer, so the final conversion is exact. Keeping the intermediate arithmetic exact also makes this a safer example to experiment with: a very long run of ones can create large prefix counts before a later invalid pair makes the complete answer zero.
For arbitrary inputs outside the final‑answer guarantee, return a bigint instead of converting it. A TypeScript return annotation does not protect a JavaScript number from rounding. The code needs a runtime with BigInt support and a TypeScript target of ES2020 or later.
Keep Only the Counts Still in Use
Each new prefix reads the preceding two counts. The whole table is helpful for explanation, but unnecessary if all we want is the final answer.
const numDecodings = (digits: string): number => {
let twoBack = 1n;
let oneBack = digits[0] === '0' ? 0n : 1n;
for (let index = 1; index < digits.length; index += 1) {
let current = digits[index] === '0' ? 0n : oneBack;
const pair = digits.slice(index - 1, index + 1);
if (pair >= '10' && pair <= '26') current += twoBack;
twoBack = oneBack;
oneBack = current;
}
return Number(oneBack);
};Before processing a digit, oneBack counts the prefix immediately before it and twoBack counts the prefix before that. current starts with the one‑digit contribution, which may be zero. We add the two‑digit contribution only when the pair is valid, then move both previous values forwards.
The order of those assignments matters. Updating oneBack to current before saving its old value would lose the count needed on the next iteration. I prefer three plainly named variables to an impressive‑looking one‑liner here. There is already enough bookkeeping in the explanation.
Both versions make O(n) iterations and at most two additions per iteration. The table holds O(n) counters; the rolling version holds a constant number. Because those counters are BigInts, that isn't the whole memory story for an unbounded generalisation: the largest count can need O(n) bits. Worst‑case bit storage is O(n²) for the table and O(n) for the rolling version, with up to O(n²) bit work for additions. The challenge caps the input at 100 digits, so those integers remain modest.
Make the Tests Argue with the Implementation
Examples without zeroes are too polite. They let several incorrect implementations pass. I want 0, 06, 10, 20, 30, 100, 101, and 2101 in the basic checks, alongside cases where both final‑piece choices are available.
My Dynamic Programming Comparison Lab compares these implementations with a separate enumeration of all possible splits on short inputs. That oracle actually forms candidate pieces and rejects anything outside the permitted encoding. It also includes long cases where the final answer is zero after very large intermediate counts, and a demonstration of the leading‑zero mistake.
Do not strip leading zeroes to make a failing test pass. Do not sort the digits either. Their order and their exact spelling are the input, not formatting to tidy away. If this were an external API, I would validate the digit‑only requirement at its boundary; these functions intentionally assume the challenge's input rules.
The Useful Distinction
The recurrence resembles a path count, but every edge has a condition. A one‑digit edge exists only for a non‑zero digit. A two‑digit edge exists only for a valid pair. The zeroes become much less mysterious once those rules live inside the recurrence rather than in a growing pile of special cases.
That is the point I would carry into another problem: decide what each count means, identify disjoint ways to extend it, and give invalid extensions a contribution of zero.