Decode Ways LeetCode Solution: Problem #91 Walkthrough

If you have solved Climbing Stairs (#70), you already know ninety percent of what Decode Ways (#91) requires. Both problems use the same Fibonacci-style recurrence where the answer at position i depends on the previous one or two positions. The twist is that Decode Ways adds string validation — not every step is available, because not every digit or pair of digits forms a valid letter code.

The decode ways leetcode problem gives you a string of digits and asks how many ways you can decode it into letters, where A = 1, B = 2, all the way up to Z = 26. For example, the string "226" can be decoded as "BZ" (2, 26), "VF" (22, 6), or "BBF" (2, 2, 6) — three total ways. This is one of the most frequently asked medium DP problems at Amazon, Google, and Meta.

In this walkthrough, you will learn the Fibonacci recurrence behind decode ways, how to handle the tricky zero cases that trip up most candidates, and how to optimize from O(n) space down to O(1). By the end, you will see why this problem is the ideal bridge between easy and medium dynamic programming.

A message has been encoded by mapping each letter to its position in the alphabet: A maps to "1", B maps to "2", and so on up to Z which maps to "26". Given a string of digits, your task is to count the total number of ways to decode it back into letters. The key constraint is that valid codes are only the integers from 1 to 26 — no leading zeros, no numbers above 26.

Consider the string "12". You can decode it as "AB" (1, 2) or as "L" (12) — two ways. The string "226" gives three ways: "BZ" (2, 26), "VF" (22, 6), and "BBF" (2, 2, 6). But the string "06" gives zero ways because "0" by itself is not a valid code and "06" is not a valid two-digit code either.

At each position in the string, you face a choice: take the current digit as a single-digit code (if it is 1 through 9), or take the current and previous digits together as a two-digit code (if they form a number between 10 and 26). This choice structure is exactly what makes it a dynamic programming problem with Fibonacci-style transitions.

The decode ways dp recurrence is beautifully simple once you see it. Define dp[i] as the number of ways to decode the first i characters of the string. At each position, you ask two questions: can I use the current digit alone, and can I use the current digit paired with the previous digit? If the single digit is valid (1-9), add dp[i-1]. If the two-digit number is valid (10-26), add dp[i-2].

This is the exact same structure as Climbing Stairs. In Climbing Stairs, dp[i] = dp[i-1] + dp[i-2] unconditionally because you can always take one step or two steps. In Decode Ways, dp[i] = dp[i-1] (if single digit valid) + dp[i-2] (if two-digit code valid). The Fibonacci recurrence is there, but with conditions on each branch.

The base cases are dp[0] = 1 (the empty prefix has exactly one way to decode — do nothing) and dp[1] depends on whether the first character is nonzero. If s[0] is "0", dp[1] = 0 because there is no valid decoding. Otherwise dp[1] = 1. From there, you iterate forward and build the answer.

The bottom-up approach builds a dp array of size n+1, where n is the length of the string. You initialize dp[0] = 1 and dp[1] = (s[0] !== "0" ? 1 : 0). Then for each position i from 2 to n, you check two conditions and accumulate the count.

For the single-digit check, look at s[i-1]. If it is between "1" and "9", that character alone is a valid code, so add dp[i-1] to dp[i]. For the two-digit check, look at the substring s[i-2..i-1]. If this two-character string represents a number between 10 and 26, add dp[i-2] to dp[i]. The final answer is dp[n].

This runs in O(n) time and O(n) space. But since dp[i] only depends on dp[i-1] and dp[i-2], you can optimize space to O(1) by keeping just two variables — exactly like optimizing Fibonacci. Use prev2 for dp[i-2] and prev1 for dp[i-1], and update them as you iterate forward.

Zeros are where Decode Ways separates candidates who understand the problem from those who do not. The digit "0" has no corresponding letter — there is no letter for zero. This means "0" by itself is never a valid single-digit code. It can only appear as the second digit of "10" or "20", which decode to J and T respectively.

When you encounter a "0" at position i, the single-digit branch contributes nothing — you do not add dp[i-1]. The only way to use that "0" is as part of a two-digit code with the preceding digit. If the preceding digit is "1" or "2", then the pair "10" or "20" is valid, so you add dp[i-2]. If the preceding digit is anything else (like "3" through "9"), the pair is invalid and dp[i] stays at zero, meaning there is no valid decoding for the entire string.

This zero handling is the core reason Decode Ways is rated medium instead of easy. Without zeros, the problem would be pure Climbing Stairs. With zeros, you need careful conditional logic at every step. Interviewers specifically watch for how you handle these edge cases — it is the difference between a hire and a no-hire on this problem.

Beyond zeros, several edge cases are worth practicing before your interview. The string "1" has exactly one decoding (A). The string "10" has exactly one decoding (J) because "1" + "0" is invalid since "0" alone has no mapping. The string "27" also has exactly one decoding (BG) because 27 exceeds 26 and cannot be a two-digit code.

A string of all ones like "1111" demonstrates the full Fibonacci growth. Each "1" can be decoded alone or paired with its neighbor, giving you Fibonacci(n+1) decodings. This is where the Climbing Stairs connection is most visible — with all valid digits, you get the exact same count as Climbing Stairs on n steps.

The string "2101" tests multiple zero interactions. Working through it: dp[0]=1, dp[1]=1 (digit "2"), dp[2]=1 (digit "1" alone or "21" — but also need "10" handling), and so on. Tracing through examples like this by hand is the best way to build confidence with the zero logic before writing code.

Decode Ways is the perfect stepping stone in your dynamic programming journey. It takes the simplest DP pattern — Fibonacci — and adds real-world constraints that force you to think carefully about validity conditions. Once you internalize this pattern of "Fibonacci with conditions," you can apply it to problems like House Robber (#198), where the condition is adjacency, or Word Break (#139), where the condition is dictionary membership.

The fibonacci string dp pattern you learn here generalizes broadly. Any problem where you make a sequence of choices (take one element or two, include or exclude, split here or there) and the number of valid options at each step depends on simple conditions follows this same recurrence structure. Recognizing this pattern instantly in an interview saves you minutes of thinking time.

Practice Decode Ways until you can write the solution without hesitation, including every zero edge case. Then move to House Robber and Word Break to see the same Fibonacci recurrence in different contexts. YeetCode flashcards drill exactly this kind of pattern recognition — instead of memorizing solutions, you build the intuition to recognize and apply the recurrence on sight.