Abstract / Summary

Find the number of ways to decode a string that may include asterisks representing any digit.

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 32% (200k+ 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 Solution class implements a decoder for strings that may contain digits and the wildcard character *. The method numDecodings returns the number of ways the input string can be interpreted as a sequence of letters where '1'-'26' map to 'A'-'Z'. The algorithm uses depth-first recursion with memoization to explore all valid partitions while handling the special semantics of *.

Core Logic

The entry point creates a length variable, a tuple representing the possible values of *, and a two-dimensional cache. The cache is indexed by the previous digit (0-9) and the current position in the string.

size = len(s)
star = (1,2,3,4,5,6,7,8,9)
cache = [[None] * size for _ in range(10)]

A nested function deeper(previous, pos) performs the recursive exploration. The parameter previous holds a pending digit that has not yet been paired; a value of 0 means there is no pending digit.

Base Condition

When the recursion reaches the end of the string, it checks whether a pending digit remains. If previous is non-zero, the path is invalid because a digit cannot stand alone; otherwise the path contributes one valid decoding.

if pos == size:
    return 0 if previous else 1

Memoization

Before any computation, the function looks up the cache. A previously computed result is returned immediately, eliminating duplicate work.

if cache[previous][pos] is not None:
    return cache[previous][pos]

Candidate Generation

If the current character is *, the algorithm treats it as any digit from 1 to 9. Otherwise it converts the character to an integer and uses that single value.

candidates = star if s[pos] == "*" else (int(s[pos]),)

Transition Rules

For each candidate digit c, the function distinguishes two situations:

When a previous digit exists (previous > 0) The two digits are combined to form a two-character number both. If both falls within the valid range 10-26, the recursion proceeds with no pending digit.

if previous > 0:
    both = previous * 10 + c
    if 10 <= both <= 26:
        total += deeper(0, pos + 1)

When there is no pending digit (previous == 0) Three branches are possible:

• If c is 1 or 2, the digit can either stand alone or start a two-digit pair, so the recursion is called both with previous = 0 (stand-alone) and with previous = c (pending).

if 1 <= c <= 2:
    total += deeper(0, pos + 1) + deeper(c, pos + 1)

• If c is 3-9, it can only stand alone, so only the previous = 0 branch is taken.

elif 3 <= c:
    total += deeper(0, pos + 1)

Modulo Reduction

After processing all candidates, the accumulated total is reduced modulo 1_000_000_007 to keep the result within integer limits.

total %= 1_000_000_007
cache[previous][pos] = total
return total

The outer method simply initiates the recursion with no pending digit at the start of the string.

return deeper(0, 0)

Edge Cases Handled

The implementation explicitly addresses several edge conditions:

• Wildcard handling - The * character expands to nine possible digits, allowing the recursion to explore each substitution without separate branching logic elsewhere.
• Trailing pending digit - The base case returns zero when the recursion finishes with a non-zero previous, ensuring that an incomplete two-digit pair does not count as a valid decoding.
• Two-digit validation - The check 10 <= both <= 26 guarantees that only legitimate letter mappings are considered when a pending digit is combined with the current digit.
• Single-digit limits - Digits 3-9 are never allowed to start a two-digit pair, matching the decoding rules where only 1 and 2 can lead to a valid two-character code.
• Empty string - When s is empty, size is zero, the initial call to deeper(0,0) immediately hits the base case and returns 1, representing the empty decoding.

Performance Optimizations

The code incorporates several techniques that improve execution speed:

• Custom memoization table - By allocating a fixed-size list of lists indexed by previous and pos, the solution avoids the overhead of Python’s functools.lru_cache decorator. Direct list access is faster than dictionary lookups used by generic caches.
• Tuple for wildcard values - Storing the nine possible digits for * in a tuple (star) provides an immutable, cache-friendly container that can be reused across recursive calls without allocation.
• Early termination of invalid two-digit combos - The condition if 10 <= both <= 26 prevents unnecessary recursive calls for out-of-range pairs, reducing the number of explored states.
• Modulo operation placed after the inner loop - Accumulating the total for all candidates before applying the modulo reduces the frequency of the relatively expensive modulo operation.
• Avoidance of string slicing - The algorithm works with the original string and an integer index, eliminating the creation of new substrings at each recursive step.

These choices collectively keep the number of recursive invocations bounded by the product of the string length and the limited range of previous values, while ensuring that each state is computed at most once.

Imagine you are holding a secret code made of numbers, where each number represents a letter of the alphabet. For instance, the number one is the letter A and the number two is B, all the way up to twenty-six for the letter Z. Sometimes the code has a star, which means it could stand for any number from one to nine.

This code acts like a detective trying to figure out all the different ways to translate that secret code. It starts at the beginning of the line of numbers and looks at what it sees. If it sees a star, it considers every possibility from one to nine. If it sees a regular number, it just uses that.

Because there can be so many ways to read the message, the code keeps a notepad called a cache. Whenever it figures out how many options come from a specific spot, it writes that number down on the page. If it ever reaches that same spot again later, it just looks at the notepad instead of doing the hard work all over again.

The process keeps moving forward, one step at a time, looking at numbers one by one or sometimes two at a time if they can form a valid letter. Every time a full message is decoded, it counts that as a success. If it gets stuck because the numbers do not make sense, it stops and tries a different path. Once it reaches the very end of the line, it adds up all the successful ways it found and keeps the number manageable by using a large limit.

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

Time: linear
As a rule of thumb, the maximum input size for one second execution time is

• factorial: up to 10 elements
• exponential: up to 20 elements
• polynomial: a few thousand elements
• loglinear: up to 100,000 elements
• linear: a few million elements
• logarithmic: a billion elements
• constant: practically unlimited

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++			Java
	leetcode.ca		Python		Java				Go
	LeetcodeHelp	C++	Python		Java
	Progiez	C++	Python		Java
github	black-shadows	C++
	charles-wangkai				Java
	everthis			JS
	fengvyi	C++
	fpdjsns	C++
	gouthampradhan				Java
	JoshCrozier			JS
	linouk23	C++
	lkwq007		Python
	lzl124631x	C++
	ruoru					Rust
	suxrobGM						C#
	trung-hn		Python
	vli02							C
	wisdompeak	C++
AlgoMonster	C++, Python, Java, TypeScript
WalkCCC	C++, Java
leetcode.ca	Go, Java, Python
LeetcodeHelp	C++, Java, Python
Progiez	C++, Java, Python
black-shadows	C++, C++
charles-wangkai	Java
everthis	JavaScript
fengvyi	C++
fpdjsns	C++
gouthampradhan	Java
JoshCrozier	JavaScript
linouk23	C++
lkwq007	Python
lzl124631x	C++
ruoru	Rust
suxrobGM	C#
trung-hn	Python
vli02	C
wisdompeak	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