Decode Ways: Memoized Recursion, JavaScript Solution, and Walkthrough
Learn Decode Ways with a memoized JavaScript dynamic programming solution, a trace of valid digit splits, complexity analysis, and zero pitfalls.
This article has an interactive companion
Don't just read it — step through it interactively, one state change at a time.
Decode Ways looks like a string problem until 226 forces the real question: how many legal ways can the same digits be partitioned? It can become 2, 2, 6, 22, 6, or 2, 26, so the answer is 3. A greedy choice cannot decide between those branches safely.
The useful reframe is to count suffixes. Once you know how many ways a remaining prefix can be decoded, every earlier choice can reuse that result. The visualizer implements that idea as top-down dynamic programming: recursive calls choose one or two trailing digits, and a memo records each remaining string only once.
The problem
Map digit strings from 1 through 26 to letters A through Z. Given a string of digits, return the number of complete decodings. A standalone 0 is never a letter; it is valid only inside 10 or 20.
Input: s = "226"
Output: 3
Explanation: "2 2 6", "22 6", and "2 26"The base case matters more than it first appears. An empty remaining string means a previous sequence of choices consumed every digit legally. That is one completed decoding, so the recursive function returns 1 rather than 0.
The brute force baseline
At every position, brute force can try a one-digit code and, when it is between 10 and 26, a two-digit code. For a string of many 1s, both branches keep being legal. The recursion tree then resembles Fibonacci growth: the same remainder such as "111" is solved again from several parents.
function countWithoutMemo(s) {
if (s === "") return 1;
let ways = 0;
if (s.at(-1) !== "0") ways += countWithoutMemo(s.slice(0, -1));
if (s.slice(-2) >= "10" && s.slice(-2) <= "26") {
ways += countWithoutMemo(s.slice(0, -2));
}
return ways;
}This follows the right recurrence, but it recomputes overlapping remainders. On a length-n string with many valid splits, it is exponential time, roughly O(2ⁿ). That is the signal to cache subproblem answers.
The key insight: the remaining string is the state
Define fn(remS) as the number of ways to decode exactly remS. Its final digit can be consumed alone when it is not 0. Its final two digits can be consumed together when the substring lies from "10" through "26". Those are the only legal last moves.
The key is that the answer depends only on remS, not on the route that reached it. Store dp[remS] after solving it. A later branch asking for the same remainder can return immediately. This is top-down memoization, even though the same recurrence can also be written as a left-to-right bottom-up table.
The optimal solution
This is the visualizer's canonical JavaScript algorithm. In particular, it uses object keys that are remaining substrings and evaluates the one-digit and two-digit conditions separately.
function numDecodings(s) {
const dp = {};
const fn = (remS) => {
if (remS === "") return 1;
if (remS in dp) return dp[remS];
const n = remS.length;
const oneDigit = remS.substring(n - 1);
const twoDigit = remS.substring(n - 2);
let ans = 0;
if (oneDigit !== "0") {
ans += fn(remS.substring(0, n - 1));
}
if (twoDigit >= "10" && twoDigit <= "26") {
ans += fn(remS.substring(0, n - 2));
}
dp[remS] = ans;
return ans;
};
return fn(s);
}Using string comparisons for twoDigit is safe here because both bounds and candidate are two-character digit strings. A one-character remainder produces its same one-character substring for twoDigit, which cannot fall in the two-digit range.
Walkthrough: s = "226"
| Remaining string | Legal final code | Recursive remainder | Ways contributed | Memoized answer |
|---|---|---|---|---|
"2" | 2 | "" | 1 | 1 |
"22" | 2 | "2" | 1 | |
"22" | 22 | "" | 1 | 2 |
"226" | 6 | "22" | 2 | |
"26" | 6 | "2" | 1 | |
"26" | 26 | "" | 1 | 2 |
"226" | 26 | "2" | 1 | 3 |
When fn("226") explores the one-digit choice 6, it learns that "22" has two decodings. The two-digit choice 26 contributes one more via "2"; that result is already memoized. The cache removes repeated work without changing the count.
Complexity
| Approach | Time | Space | Why |
|---|---|---|---|
| Brute-force recursion | O(2ⁿ) | O(n) call stack | repeated split trees grow exponentially |
| Memoized visualizer solution | O(n²) | O(n²) | up to n substring states, with substring creation and storage proportional to length |
| Indexed or rolling DP variant | O(n) | O(n) or O(1) | avoids allocating substring keys |
The visualizer code is algorithmically memoized, but JavaScript substring allocation makes its literal complexity less tidy than an indexed implementation. Its teaching value is that the state is unmistakable: each cache key is the unsolved remainder.
There is also a useful correctness argument. Every valid decoding of a nonempty remainder ends with either one legal digit or one legal two-digit code; those cases are disjoint, so adding their counts neither misses nor double-counts a decoding. Each recursive call shortens the string, eventually reaching the empty base case. Memoization is safe because equal remS values have equal sets of legal suffix splits.
Common mistakes
- Treating
0as a one-digit option."06"has no valid decoding; only the pairs10and20can include zero. - Returning 0 for the empty remainder. That erases a successful completed branch. The empty string must contribute one way.
- Accepting
27. Two digits are valid only through 26, so"27"must be split as2, 7. - Caching before both branches finish. Store the total only after adding every legal final move.
- Assuming memoization changes the recurrence. It only prevents solving identical remainders twice.
Where this pattern shows up next
- Fibonacci Number introduces the overlapping-subproblem recurrence in its smallest form.
- Climbing Stairs counts legal one-step and two-step choices with the same Fibonacci shape.
- Min Cost Climbing Stairs turns the count recurrence into a minimum-cost recurrence.
- House Robber uses include-or-skip choices and memoizable suffix states.
You can also step through it interactively to watch calls return and the memo fill.
FAQ
Why is Decode Ways dynamic programming?
Different split choices reach the same remaining digit string. The number of decodings from that remainder is always identical, so memoization stores it once and lets every caller reuse it.
Why does an empty string return 1 in Decode Ways?
It represents one successfully completed parsing path. Returning 1 lets the final valid one-digit or two-digit choice count as a complete decoding; returning 0 would make every branch disappear.
How should zero be handled in Decode Ways?
Zero cannot be decoded alone. It contributes only when paired as 10 or 20; combinations such as 30, 00, and a leading 0 cannot form a valid code at that point.
Can Decode Ways be solved in O(1) extra space?
Yes. A bottom-up version needs only the previous two counts, because each position depends on the one-digit and two-digit transitions immediately before it. The visualizer instead uses memoized substring states to make the recursive choices visible.
What inputs should I use to test Decode Ways?
Test "12" for both one- and two-digit choices, "226" for several branches, "10" and "20" for legal zeros, and "06" or "100" for impossible paths. A long run like "11111" is especially useful for confirming that overlapping remainders are reused.
Make it stick: run this one yourself
Don't just read it — step through it interactively, one state change at a time.