Abstract / Summary

Count the ways to decode a string of digits into letters based on a fixed mapping from digits to letters.

Note

The full problem description, including helpful examples, can be found on LeetCode.

This problem is ranked as

and has an acceptance rate of about 38% (4+ million submissions).

Typical patterns to solve this problem:

• Dynamic Programming
• String

Every single line of code was written by me, 100% from scratch, between August 2023 and August 2024.
However, two years later I set up this website and used various AI tools to generate most of the walkthrough / explanations below.

See this dedicated page for more details.

Overview

The provided implementation solves the classic decoding problem where a numeric string is interpreted as letters (1 → 'A', 2 → 'B', …, 26 → 'Z'). The method numDecodings computes the total number of valid ways to decode the input string s. It employs a dynamic-programming map dp where the key represents a position in the string (the number of characters processed) and the value stores the count of decoding ways up to that position. The algorithm iterates once over the characters, updating the map based on the current digit and its predecessor, and returns the final count for the full length of the string.

Key Steps

The initialization creates a base case for an empty prefix:

map<int, int> dp;
dp[0] = 1;

The main loop processes each character by index i:

for (int i = 0; i < s.size(); i++)
{
    auto c = s[i];
    // handling logic follows
}

When the current character is '0', the code checks whether it can form a valid two-digit number with the preceding character. If the preceding character is '1' or '2', the zero can be paired; otherwise the function returns 0 indicating an impossible decoding. The valid pairing contributes the count from two positions back:

if (c == '0')
{
    if (i == 0 || s[i-1] == '0' || s[i-1] > '2')
        return 0;
    dp[i+1] += dp[i-1];
    continue;
}

For non-zero digits, the count from the previous position is always added, reflecting the possibility of decoding the current digit as a standalone letter:

dp[i+1] += dp[i];

If the current index is not the first character, the algorithm examines the two-character window formed with the previous digit. When the previous digit is '1', any current digit creates a valid two-digit number (10-19), so the count from two positions back is added:

if (s[i-1] == '1')
{
    dp[i+1] += dp[i-1];
    continue;
}

When the previous digit is '2' and the current digit lies between '1' and '6', the pair forms a valid number (21-26). The same two-step contribution is applied:

if (s[i-1] == '2' && c >= '1' && c <= '6')
{
    dp[i+1] += dp[i-1];
    continue;
}

After the loop finishes, the result for the full string length is retrieved:

return dp[s.size()];

Edge Cases Handled

The code explicitly guards against leading zeros. If the first character is '0', the early return inside the zero-handling block triggers because i == 0. This prevents any decoding path from starting with an invalid digit.

When a '0' appears later in the string, the algorithm validates that it is part of a legal '10' or '20' pair. The condition s[i-1] == '0' || s[i-1] > '2' filters out illegal combinations such as '30' or '00'. In those scenarios the function returns 0, indicating that no decoding exists.

The two-digit validation for '2' ensures that only numbers up to 26 are considered. Digits '7' through '9' following a '2' are ignored for the two-digit contribution, preserving correctness for inputs like "27" where only the '2' and '7' can be decoded separately.

The continuation statements (continue) after each successful update prevent double counting within the same iteration, guaranteeing that each decoding path is accounted for exactly once per relevant condition.

Performance Optimizations

The implementation uses a map<int, int> to store intermediate results. Because the keys are sequential integers from 0 to s.size(), the map provides O(log n) access, but the constant factor remains low due to the small range of keys. This choice avoids the need for a separate vector allocation and leverages the map’s automatic handling of missing keys (default-initialized to zero), simplifying the update logic.

The algorithm processes the input string in a single pass, performing only a constant amount of work per character. Early termination occurs when an impossible '0' configuration is detected, allowing the function to exit without scanning the remainder of the string. This early exit reduces unnecessary work for invalid inputs.

By reusing the same dp map throughout the loop and only inserting entries for i+1, the code minimizes memory churn. No additional temporary structures are created inside the loop, keeping the runtime overhead minimal.

Overall, the solution balances clarity with efficient use of standard containers, delivering a linear-time decoding count while handling all special cases directly within the iteration.

Imagine you are walking down a path made of number blocks, and your goal is to count how many different ways you can jump from the start to the end. Each number block acts like a letter, where one is A, two is B, and so on, all the way up to twenty-six being Z.

The code uses a special notebook to keep track of how many ways you have found to reach each step along the way. It starts by saying there is one way to be at the beginning before you even take a step.

As you step on each number, you look at the blocks ahead of you. If you see a single number, you can treat it as one letter, like picking up a single toy. If you look at the current block together with the one right before it, sometimes they make a bigger number that happens to be a letter too, like putting two puzzle pieces together to make a whole picture.

When the code sees a zero, it knows that zero cannot be a letter on its own, so it checks if the zero belongs to the number before it to make a ten or a twenty. If it cannot do that, it stops because there are no ways to finish the path.

For every other number, the code adds up all the different ways to get to that spot. It looks at the ways to reach the spot just before and adds them to its notebook. If a pair of numbers forms a letter between ten and twenty-six, it also includes the ways to reach the spot two steps back. By the time you reach the very end, the notebook tells you exactly how many different stories can be told using those numbers.

Several LLMs ranked my code quality on a scale from 1 (very poor) to 10 (outstanding):

not analyzed yet

I wrote a basic crawler to find other solutions to that problem.
Obviously, I did that after I solved the problem myself.

In general, AlgoMonster and WalkCCC solutions are high-quality and always worth a look.
I haven't checked most of the other solutions, but they might be helpful as well.

And of course, the LeetCode forum is always a good place (or even the best) to look for alternative approaches.

(click on a column header to sort the table)

	author
author	solutions
www	AlgoMonster	C++	Python	Java						TS
	WalkCCC	C++	Python	Java
	leetcode.ca	C++	Python	Java	C#				Go	TS
	LeetcodeHelp	C++	Python	Java
	MemoryLimitExceeded	C++	Python
	Progiez	C++	Python	Java
github	aylei						Rust
	begeekmyfriend					C
	BigEggStudy				C#
	black-shadows	C++
	bujosa		Python
	charles-wangkai			Java
	chenyanzhe	C++
	everthis							JS
	FelixFan1122				C#
	fengvyi	C++
	gaosq0604		Python
	Garvit244		Python
	gouthampradhan			Java
	halfrost								Go
	haoel	C++
	JoshCrozier							JS
	keineahnung2345	C++
	lennylxx					C
	linouk23	C++
	lkwq007		Python
	luangong	C++
	lzl124631x	C++
	MacJim	C++
	qiyuangong		Python
	ruoru						Rust
	suxrobGM				C#
	trung-hn		Python
	varunu28			Java
	vli02					C
	vthwang			Java
	wisdompeak	C++
	zfang399	C++
AlgoMonster	C++, Python, Java, TypeScript
WalkCCC	C++, Python, Java
leetcode.ca	C++, C#, Go, Java, Python, TypeScript
LeetcodeHelp	C++, Java, Python
MemoryLimitExceeded	Python, C++
Progiez	C++, Java, Python
aylei	Rust
begeekmyfriend	C
BigEggStudy	C#
black-shadows	C++, C++
bujosa	Python
charles-wangkai	Java
chenyanzhe	C++
everthis	JavaScript
FelixFan1122	C#
fengvyi	C++
gaosq0604	Python
Garvit244	Python
gouthampradhan	Java
halfrost	Go
haoel	C++
JoshCrozier	JavaScript
keineahnung2345	C++
lennylxx	C
linouk23	C++
lkwq007	Python
luangong	C++
lzl124631x	C++
MacJim	C++
qiyuangong	Python
ruoru	Rust
suxrobGM	C#
trung-hn	Python
varunu28	Java
vli02	C
vthwang	Java
wisdompeak	C++
zfang399	C++

There are a few extra pages giving you some insights into my setup:

• Tech Stack - my development environment and tools
• AI - how AI helped me create this website (NOT solving the problems)
• Progress - progression over time
• Quality - code quality