Ways to decode a string of digits
A message of letters was encoded with A → 1, B → 2, …, Z → 26 and the numbers written one after another. Given the
digit string s, return the number of ways to decode it. A code may not have a leading zero: "06" is not "F",
and "0" alone decodes to nothing.
Examples
| Input | Output | Why |
|---|---|---|
s = "12" | 2 | "AB" (1, 2) or "L" (12). |
s = "226" | 3 | 2 2 6, 22 6, 2 26. |
s = "06" | 0 | A leading zero makes the whole string undecodable. |
Constraints
- 1 ≤ s.length ≤ 100
- s contains only digits
Hints
Hint 1
ways[i] = number of decodings of s[i:]. ways[n] = 1 (the empty suffix).
Hint 2
Take one digit if it is not 0; take two if they form 10..26.
Hint 3
Only the next two entries are read: keep two variables.
Where people lose marks
- Treating "0" as a valid single code.
- Accepting "05" as a two-digit code.
- Accepting 27 or above as two digits.
Dry run on "2101"
Read it one frame at a time, the way you would trace the code on paper in an interview. Each frame shows the state after the step it describes.
-
Step 1 / 5s20110213∅4ways·0·1·2·314
The empty suffix has one decoding.
-
Step 2 / 5s20110213∅4ways·0·1·21314
Position 3: one digit "1" gives 1; two digits "1" are not a code. ways = 1.
-
Step 3 / 5s20110213∅4ways·0·1021314
Position 2: one digit "0" is not allowed; two digits "01" are not a code. ways = 0.
-
Step 4 / 5s20110213∅4ways·011021314
Position 1: one digit "1" gives 0; two digits "10" give 1. ways = 1.
-
Step 5 / 5s20110213∅4ways1011021314
Position 0: one digit "2" gives 1; two digits "21" give 0. ways = 1. The answer is 1.
How to think about it
Let ways[i] count the decodings of the suffix starting at i, with ways[n] = 1. At position i
the first letter uses one digit (allowed unless it is '0') or two digits (allowed if they form 10 to 26), so
ways[i] = [s[i] ≠ '0'] · ways[i + 1] + [10 ≤ s[i..i+1] ≤ 26] · ways[i + 2]. Fill from the right. The zero rules
are the whole difficulty: a '0' can only be the second digit of 10 or 20.
Complexity. Time O(n) · Space O(1)
The solution, in six languages
Each one is compiled and run against the test table before it is published. Java is reviewed by hand.
def num_decodings(s):
one_ahead, two_ahead = 1, 0 # ways[i + 1] and ways[i + 2]; ways[n] = 1
for i in range(len(s) - 1, -1, -1):
here = 0
if s[i] != '0':
here = one_ahead # a one-digit code
if i + 1 < len(s) and int(s[i:i + 2]) <= 26:
here += two_ahead # a two-digit code, 10..26
one_ahead, two_ahead = here, one_ahead
return one_ahead#include <string>
long long solve(std::string s) {
long long oneAhead = 1, twoAhead = 0; // ways[i + 1], ways[i + 2]
for (int i = (int)s.size() - 1; i >= 0; --i) {
long long here = 0;
if (s[i] != '0') {
here = oneAhead; // one digit
if (i + 1 < (int)s.size() && (s[i] - '0') * 10 + (s[i + 1] - '0') <= 26) here += twoAhead;
}
twoAhead = oneAhead;
oneAhead = here;
}
return oneAhead;
}class Solution {
public long numDecodings(String s) {
long oneAhead = 1, twoAhead = 0; // ways[i + 1], ways[i + 2]
for (int i = s.length() - 1; i >= 0; i--) {
long here = 0;
if (s.charAt(i) != '0') {
here = oneAhead; // one digit
if (i + 1 < s.length() && (s.charAt(i) - '0') * 10 + (s.charAt(i + 1) - '0') <= 26) here += twoAhead;
}
twoAhead = oneAhead;
oneAhead = here;
}
return oneAhead;
}
}function numDecodings(s) {
let oneAhead = 1, twoAhead = 0; // ways[i + 1], ways[i + 2]
for (let i = s.length - 1; i >= 0; i--) {
let here = 0;
if (s[i] !== '0') {
here = oneAhead; // one digit
if (i + 1 < s.length && Number(s.slice(i, i + 2)) <= 26) here += twoAhead; // two digits
}
[oneAhead, twoAhead] = [here, oneAhead];
}
return oneAhead;
}fn solve(s: &str) -> i64 {
let d: Vec<i64> = s.bytes().map(|b| (b - b'0') as i64).collect();
let (mut one_ahead, mut two_ahead) = (1i64, 0i64); // ways[i + 1], ways[i + 2]
for i in (0..d.len()).rev() {
let mut here = 0;
if d[i] != 0 {
here = one_ahead; // one digit
if i + 1 < d.len() && d[i] * 10 + d[i + 1] <= 26 {
here += two_ahead; // two digits
}
}
two_ahead = one_ahead;
one_ahead = here;
}
one_ahead
}import Data.Char (digitToInt)
solve :: String -> Int
solve s = fst (go s)
where
-- go returns (ways for this suffix, ways for the suffix one shorter)
go [] = (1, 0)
go (c : rest) =
let (w1, w2) = go rest
one = if c /= '0' then w1 else 0
two = case rest of
(d : _) | c /= '0' && digitToInt c * 10 + digitToInt d <= 26 -> w2
_ -> 0
in (one + two, w1)
Variants to try
- The string may contain "*" standing for any digit 1–9 (answer modulo 10⁹ + 7).
- Return all decodings for short strings.
- Decode from the left with ways[i] for prefixes instead.
Next problems
The cheapest way up a staircase
Each step has a cost; climb one or two steps at a time; start on step 0 or 1. Return the cheapest way past the top.
Open the problem → Medium15 minCan you reach the last position?
nums[i] is the furthest jump from position i. Can you get from the first position to the last? A reachability DP that collapses to one variable.
Open the problem → Medium15 minLargest sum with no two chosen positions adjacent
Two states, one recurrence, O(1) memory. The example to reach for when someone asks you to explain dynamic programming.
Open the problem →Write a solution and run it against the real test table.
Keep going
The cheapest way up a staircase
Each step has a cost; climb one or two steps at a time; start on step 0 or 1. Return the cheapest way past the top.
Open the problem → Medium15 minCan you reach the last position?
nums[i] is the furthest jump from position i. Can you get from the first position to the last? A reachability DP that collapses to one variable.
Open the problem → Medium15 minLargest sum with no two chosen positions adjacent
Two states, one recurrence, O(1) memory. The example to reach for when someone asks you to explain dynamic programming.
Open the problem → Dynamic programmingThe pattern behind it
Write the recursion, notice the repeats, fill a table in an order that makes each entry final.
Read the pattern →Preparing for a real process? Quant interview preparation, or book a free 20-minute call.