A is 1, B is 2, up to Z which is 26. Given a string of digits, how many ways can it be decoded?
"12" → 2 ("AB" = 1,2 or "L" = 12)"226" → 3 ("BZ", "VF", "BBF")"06" → 0 (no letter is 0, and "06" is not a valid 6)
Restating the Problem: Imagine you intercept a secret numerical message where A=1, B=2 ... Z=26. Because there are no spaces between the numbers, the message is ambiguous. For example, 12 could be 1, 2 (A, B) or 12 (L). Your task is to calculate the total number of distinct ways this string of digits could be translated back into letters.
Constraints to Note:
The string length is up to 100.
The string contains only digits 0-9.
The answer is guaranteed to fit in a 32-bit integer.
The naive approach is a recursive depth-first search. At each character, you try parsing just 1 digit, and then recursively decode the rest of the string. Then you try parsing 2 digits, and recursively decode the rest. This means each step branches into 2 possibilities, giving an O(2^N) time complexity. With N=100, 2^{100} is unfathomably large. The waste here is overlapping subproblems: if you decode "12" and are left with "345", and then you decode "1", then "2" and are left with "345", you evaluate "345" multiple times. We can cache this, or build it bottom-up.
Same shape as 4.23.1 Climbing Stairs — at each position you consume one digit or two — but now each move has a condition.
Let dp[i] be the number of ways to decode the first i characters.
dp[i] = \underbrace{dp[i-1] \ \text{if the last digit is 1–9}}_{\text{take one digit}} \ + \ \underbrace{dp[i-2] \ \text{if the last two form 10–26}}_{\text{take two digits}}
The whole problem is the validity conditions, and each has an input designed to catch you.
A single digit is valid unless it is 0. There is no letter 0, so "0" alone decodes zero ways.
A pair is valid only between 10 and 26. That means the first digit must be 1 or 2, and if it is 2 the second must be at most 6.
A leading zero in a pair is invalid."06" is not 6 — the pair must start with 1 or 2, so 0 never begins a valid two-digit code. This is the case that breaks naive solutions, and "06" is on the test set for exactly that reason.
One consequence follows: a 0 in the input can only ever be decoded as part of 10 or 20. Any other 0 makes the whole string undecodable, and the count drops to zero and stays there.
class Solution: def numDecodings(self, s: str) -> int: if not s or s[0] == '0': # (1) return 0 two_back, one_back = 1, 1 # (2) dp[0] = 1 (empty), dp[1] = 1 for i in range(1, len(s)): # (3) current = 0 # (4) if s[i] != '0': # (5) take one digit current += one_back two_digit = int(s[i - 1: i + 1]) # (6) if 10 <= two_digit <= 26: # (7) take two digits current += two_back two_back, one_back = one_back, current # (8) return one_back # (9)
ts
function numDecodings(s: string): number { if (!s || s[0] === '0') return 0; // (1) let twoBack = 1, oneBack = 1; // (2) for (let i = 1; i < s.length; i++) { // (3) let current = 0; // (4) if (s[i] !== '0') current += oneBack; // (5) const twoDigit = Number(s.slice(i - 1, i + 1)); // (6) if (twoDigit >= 10 && twoDigit <= 26) current += twoBack; // (7) twoBack = oneBack; // (8) oneBack = current; } return oneBack; // (9)}
Here dp[k] means "the number of ways to decode the first k characters".
(1) An empty string, or one starting with '0', cannot be decoded. No letter's code starts with 0.
(2) two_back is dp[0] and one_back is dp[1].dp[0] = 1, because there is exactly one way to decode nothing: do nothing. dp[1] = 1, because the first character is a valid digit 1 to 9.
(3) Work through the rest of the string, one character at a time.
(4) Ways to decode up to and including character i, starting from 0.
(5) Use character i on its own. That works for any digit except '0'. It adds every way of decoding everything before it, one_back.
(6) The two-digit number made by characters i − 1 and i.
(7) Use those two characters together as one letter. That works for 10 to 26. It adds every way of decoding everything before the pair, two_back. A pair like "06" is the number 6, which is below 10, so it is correctly refused.
(8) Slide forward by one character.
(9) The number of ways to decode the whole string.
dp[0] = 1 is the base case that trips people up. The empty string has exactly one decoding — the empty one. It looks like it should be 0, but making it 1 is what allows a valid two-digit code at the very start to be counted: for "12", the pair 12 contributes dp[0] = 1, which is correct.
The s[0] == '0' guard rejects a string that cannot start at all.
current starts at 0 every iteration, so a position where neither move is legal correctly yields 0 — and from then on every later position sees a 0 and stays 0. The zero propagates by itself, which is exactly right.
10 <= two_digit <= 26 covers the leading-zero rule for free, because "06" is 6, which is below 10.
Now "06": the guard fires on s[0] == '0' and returns 0 immediately.
And "106": at i = 1 the char is 0, so no one-digit move; the pair 10 is valid, so current = dp[0] = 1. At i = 2 the char is 6, so current = dp[1] = 1; the pair 06 is invalid. Answer 1 — "JF" ✓.
Time Complexity Derivation: We iterate through the string of N digits exactly once. Inside the loop, we are doing simple character checks and integer conversions on slices of length 2, which take O(1) time. Thus, the total time is strictly O(N).
Space Complexity Derivation: Although a full DP array would take O(N) space, we optimize it down to O(1) because dp[i] only relies on dp[i-1] and dp[i-2]. We just keep two variables (one_back and two_back), meaning the memory footprint remains constant regardless of the string length.
Decode Ways II — the input may contain *, meaning any digit from 1 to 9. The same recurrence with counted possibilities instead of yes-or-no, and the arithmetic becomes fiddly. A good demonstration that the shape survives while the conditions get harder.
Climbing Stairs — this recurrence with no conditions at all. 4.23.1.
Word Break — the same "can I split this string" idea, but the pieces can be any length and are checked against a dictionary. 4.23.10.
The family: split a string into valid pieces. Fixed piece lengths give this problem; arbitrary lengths give Word Break; palindromic pieces give Palindrome Partitioning. Same skeleton, different validity test.
"Why is dp[0] = 1?" The empty string has one decoding, and that base value is what lets a leading two-digit code be counted.
"What does '06' do?" Zero ways. The pair rule requires 10 to 26, so a leading zero can never form a valid pair.
"Where can a 0 legally appear?" Only as the second digit of 10 or 20.
"Walk through '2101'." A good test — the answer is 1, and it exercises both zero rules.
"O(1) space?" Two variables, since only the previous two values are read.
One thing to volunteer: enumerate the three validity rules before writing code, and name the input that breaks each. This problem is not hard once the rules are written down; it is hard when you discover them one failing test at a time.
Next:4.23.8 Coin Change — the classic optimisation DP, and the clearest proof that greedy fails.