Language Selection
Choose your preferred programming language
Decode Ways
Problem Statement
A message made of capital letters was encoded by replacing each letter with its position in the alphabet: A becomes "1", B becomes "2", and so on up to Z, which becomes "26". The numbers were then written next to each other with no separators.
Given the resulting digit string s, return how many different letter messages could have produced it. A valid decoding splits s into pieces where every piece is a number from 1 to 26 written without a leading zero. So "06" is not a valid piece, and a lone "0" can only appear as the second digit of "10" or "20". If no valid split exists, the answer is 0.
Examples
Example 1:
Input: s = "17"
Output: 2
Explanation: "17" can be read as 1 7 ("AG") or as 17 ("Q").
Example 2:
Input: s = "2101"
Output: 1
Explanation: The only valid split is 2 10 1 ("BJA"). Splitting as 21 0 1
leaves a lone 0, and "01" has a leading zero.
Example 3:
Input: s = "308"
Output: 0
Explanation: The 0 cannot stand alone, and 30 is larger than 26,
so the string cannot be decoded at all.
Constraints
1 <= s.length <= 100scontains only digits and may contain leading zeros- The answer fits in a signed 32-bit integer
Approach 1: Recursion with Memoization
Algorithm
Think of decoding as walking from left to right. At index i you have at most two choices: read one digit, or read two digits. Reading one digit is allowed when s[i] is not '0'. Reading two digits is allowed when the pair forms a number from 10 to 26. The number of decodings of the suffix starting at i is the sum of the counts for the choices that are allowed.
Plain recursion repeats the same suffixes many times and grows exponentially (like naive Fibonacci). Caching each suffix’s answer makes every index get computed once.
- Define
ways(i)= number of decodings ofs[i:]. - If
i == n, return 1: we used the whole string, which is one complete decoding. - If
s[i] == '0', return 0: no letter starts with a zero. - Otherwise
ways(i) = ways(i + 1), plusways(i + 2)ifs[i..i+1]is between 10 and 26. - Store each result so it is computed once. The answer is
ways(0).
Every suffix this recursion visits can be reached by a valid decoding of the prefix before it, so no intermediate count is larger than the final answer. A 32-bit int is therefore safe here.
Implementation
Python:
from functools import lru_cache
class Solution:
def numDecodings(self, s: str) -> int:
n = len(s)
@lru_cache(maxsize=None)
def ways(i: int) -> int:
if i == n: # consumed the whole string: one decoding
return 1
if s[i] == '0': # no letter is encoded with a leading zero
return 0
total = ways(i + 1) # read one digit
# read two digits when they form 10..26
if i + 1 < n and (s[i] == '1' or (s[i] == '2' and s[i + 1] <= '6')):
total += ways(i + 2)
return total
return ways(0)
Java:
import java.util.Arrays;
class Solution {
private String s;
private int[] memo;
public int numDecodings(String s) {
this.s = s;
memo = new int[s.length()];
Arrays.fill(memo, -1); // -1 means "not computed yet"
return ways(0);
}
private int ways(int i) {
if (i == s.length()) return 1; // one complete decoding
if (s.charAt(i) == '0') return 0; // a piece cannot start with 0
if (memo[i] != -1) return memo[i];
int total = ways(i + 1); // read one digit
if (i + 1 < s.length()) {
char a = s.charAt(i), b = s.charAt(i + 1);
if (a == '1' || (a == '2' && b <= '6')) {
total += ways(i + 2); // read two digits (10..26)
}
}
memo[i] = total;
return total;
}
}
Go:
func numDecodings(s string) int {
n := len(s)
memo := make([]int, n)
for i := range memo {
memo[i] = -1 // -1 means "not computed yet"
}
var ways func(i int) int
ways = func(i int) int {
if i == n {
return 1 // consumed the whole string: one decoding
}
if s[i] == '0' {
return 0 // a piece cannot start with 0
}
if memo[i] != -1 {
return memo[i]
}
total := ways(i + 1) // read one digit
if i+1 < n && (s[i] == '1' || (s[i] == '2' && s[i+1] <= '6')) {
total += ways(i + 2) // read two digits (10..26)
}
memo[i] = total
return total
}
return ways(0)
}
JavaScript:
/**
* @param {string} s
* @return {number}
*/
var numDecodings = function (s) {
const n = s.length;
const memo = new Array(n).fill(-1); // -1 means "not computed yet"
const ways = (i) => {
if (i === n) return 1; // one complete decoding
if (s[i] === '0') return 0; // a piece cannot start with 0
if (memo[i] !== -1) return memo[i];
let total = ways(i + 1); // read one digit
if (i + 1 < n && (s[i] === '1' || (s[i] === '2' && s[i + 1] <= '6'))) {
total += ways(i + 2); // read two digits (10..26)
}
memo[i] = total;
return total;
};
return ways(0);
};
C#:
using System;
public class Solution {
private string s;
private int[] memo;
public int NumDecodings(string s) {
this.s = s;
memo = new int[s.Length];
Array.Fill(memo, -1); // -1 means "not computed yet"
return Ways(0);
}
private int Ways(int i) {
if (i == s.Length) return 1; // one complete decoding
if (s[i] == '0') return 0; // a piece cannot start with 0
if (memo[i] != -1) return memo[i];
int total = Ways(i + 1); // read one digit
if (i + 1 < s.Length && (s[i] == '1' || (s[i] == '2' && s[i + 1] <= '6'))) {
total += Ways(i + 2); // read two digits (10..26)
}
memo[i] = total;
return total;
}
}
C++:
#include <string>
#include <vector>
using namespace std;
class Solution {
public:
int numDecodings(string s) {
vector<int> memo(s.size(), -1); // -1 means "not computed yet"
return ways(s, 0, memo);
}
private:
int ways(const string& s, size_t i, vector<int>& memo) {
if (i == s.size()) return 1; // one complete decoding
if (s[i] == '0') return 0; // a piece cannot start with 0
if (memo[i] != -1) return memo[i];
int total = ways(s, i + 1, memo); // read one digit
if (i + 1 < s.size() && (s[i] == '1' || (s[i] == '2' && s[i + 1] <= '6'))) {
total += ways(s, i + 2, memo); // read two digits (10..26)
}
memo[i] = total;
return total;
}
};
Complexity Analysis
- Time: O(n). Each index is computed once, and each computation does constant work.
- Space: O(n) for the memo table plus a recursion stack up to n frames deep (at most 100 here).
Approach 2: Bottom-Up DP with Two Variables (Optimal)
Algorithm
Flip the direction and count decodings of prefixes. Let dp[i] be the number of ways to decode the first i characters. The last piece of any decoding of s[0..i-1] is either one digit or two digits:
- If
s[i-1]is not'0', every decoding of the firsti-1characters extends by one letter, so adddp[i-1]. - If
s[i-2..i-1]is between 10 and 26, every decoding of the firsti-2characters extends by one letter, so adddp[i-2].
This is the Climbing Stairs recurrence with conditions attached. Each step only looks two entries back, so two variables are enough.
- If
s[0] == '0', return 0. - Set
prev2 = 1(the empty prefix) andprev1 = 1(the first character). - For each
ifrom 1 ton - 1, computecurfrom the two rules above usings[i]and the pairs[i-1..i]. - If
curis 0, return 0 right away: once a prefix cannot be decoded, no longer prefix can be either. - Shift:
prev2 = prev1,prev1 = cur. Returnprev1.
Why the typed languages cap the counters: a prefix count can be larger than the final answer. In "110", the prefix "11" has 2 decodings but the whole string has only 1, because the trailing 0 forces the last piece to be "10". For a decodable string, every prefix count is at most twice the final answer: a count can only drop at a forced "10" or "20", and then only to the count from one step earlier, which is at least half of what it drops from. Since the answer fits in 32 bits, the counts of a decodable string stay at or below 2 * (2^31 - 1). An undecodable string is different. In "1" repeated 98 times followed by "30", the prefix counts grow like Fibonacci numbers, past even 2^63, before the dead "30" is reached. So Java, Go, C# and C++ clamp every count at CAP = 2^33 (anything above 2 * (2^31 - 1) works). A decodable string never reaches the cap, so its answer is exact. For an undecodable string, clamping never turns a count into 0, so the dead-prefix check in step 4 still returns 0, and no 64-bit addition can overflow (which would be undefined behaviour in C++). Python needs no cap because its integers are unbounded, and JavaScript needs none because a count is exactly 0 only when both terms are switched off, while for a decodable string every count stays far below 2^53 and is exact.
Implementation
Python:
class Solution:
def numDecodings(self, s: str) -> int:
if s[0] == '0':
return 0
prev2, prev1 = 1, 1 # ways for the empty prefix and for s[0]
for i in range(1, len(s)):
cur = 0
if s[i] != '0': # last piece is the single digit s[i]
cur = prev1
if 10 <= int(s[i - 1:i + 1]) <= 26: # last piece is s[i-1..i]
cur += prev2
if cur == 0: # this prefix is undecodable, so is the rest
return 0
prev2, prev1 = prev1, cur
return prev1
Java:
class Solution {
public int numDecodings(String s) {
if (s.charAt(0) == '0') return 0;
// Prefix counts can exceed the answer (and 2^63 on undecodable input),
// so clamp them at CAP; a decodable string never gets near it
final long CAP = 1L << 33;
long prev2 = 1, prev1 = 1; // empty prefix, first character
for (int i = 1; i < s.length(); i++) {
long cur = 0;
if (s.charAt(i) != '0') cur = prev1; // one-digit last piece
int two = (s.charAt(i - 1) - '0') * 10 + (s.charAt(i) - '0');
if (two >= 10 && two <= 26) cur += prev2; // two-digit last piece
if (cur > CAP) cur = CAP; // saturate; never makes 0
if (cur == 0) return 0; // dead prefix
prev2 = prev1;
prev1 = cur;
}
return (int) prev1;
}
}
Go:
func numDecodings(s string) int {
if s[0] == '0' {
return 0
}
// Prefix counts can exceed the answer (and 2^63 on undecodable input),
// so clamp them at capCount; a decodable string never gets near it
const capCount = 1 << 33
prev2, prev1 := 1, 1 // empty prefix, first character
for i := 1; i < len(s); i++ {
cur := 0
if s[i] != '0' {
cur = prev1 // one-digit last piece
}
two := int(s[i-1]-'0')*10 + int(s[i]-'0')
if two >= 10 && two <= 26 {
cur += prev2 // two-digit last piece
}
if cur > capCount {
cur = capCount // saturate; never makes 0
}
if cur == 0 {
return 0 // dead prefix: nothing after it can be decoded
}
prev2, prev1 = prev1, cur
}
return prev1
}
JavaScript:
/**
* @param {string} s
* @return {number}
*/
var numDecodings = function (s) {
if (s[0] === '0') return 0;
let prev2 = 1, prev1 = 1; // empty prefix, first character
for (let i = 1; i < s.length; i++) {
let cur = 0;
if (s[i] !== '0') cur = prev1; // one-digit last piece
const two = Number(s[i - 1]) * 10 + Number(s[i]);
if (two >= 10 && two <= 26) cur += prev2; // two-digit last piece
if (cur === 0) return 0; // dead prefix
prev2 = prev1;
prev1 = cur;
}
return prev1;
};
C#:
public class Solution {
public int NumDecodings(string s) {
if (s[0] == '0') return 0;
// Prefix counts can exceed the answer (and 2^63 on undecodable input),
// so clamp them at CAP; a decodable string never gets near it
const long CAP = 1L << 33;
long prev2 = 1, prev1 = 1; // empty prefix, first character
for (int i = 1; i < s.Length; i++) {
long cur = 0;
if (s[i] != '0') cur = prev1; // one-digit last piece
int two = (s[i - 1] - '0') * 10 + (s[i] - '0');
if (two >= 10 && two <= 26) cur += prev2; // two-digit last piece
if (cur > CAP) cur = CAP; // saturate; never makes 0
if (cur == 0) return 0; // dead prefix
prev2 = prev1;
prev1 = cur;
}
return (int)prev1;
}
}
C++:
#include <string>
using namespace std;
class Solution {
public:
int numDecodings(string s) {
if (s[0] == '0') return 0;
// Prefix counts can exceed the answer (and 2^63 on undecodable input),
// so clamp them at CAP; a decodable string never gets near it
const long long CAP = 1LL << 33;
long long prev2 = 1, prev1 = 1; // empty prefix, first character
for (size_t i = 1; i < s.size(); i++) {
long long cur = 0;
if (s[i] != '0') cur = prev1; // one-digit last piece
int two = (s[i - 1] - '0') * 10 + (s[i] - '0');
if (two >= 10 && two <= 26) cur += prev2; // two-digit last piece
if (cur > CAP) cur = CAP; // saturate; never makes 0
if (cur == 0) return 0; // dead prefix
prev2 = prev1;
prev1 = cur;
}
return static_cast<int>(prev1);
}
};
Complexity Analysis
- Time: O(n). One pass over the string with constant work per character.
- Space: O(1). Only two running counts are kept.
Key Insights
- Two choices per step: at every position you either read one digit or two. That makes the count a Fibonacci-like sum of the two previous states.
- Zeros are the whole difficulty: a
'0'can never be read alone, so it must join the digit before it, and only"10"and"20"are legal. - Validity rules: one-digit piece:
s[i] != '0'. Two-digit piece: first digit'1', or first digit'2'and second digit'0'to'6'. - Dead prefixes stay dead: if a prefix has zero decodings, every longer prefix also has zero, which justifies the early return.
Edge Cases
- Leading zero (
"0","06"): the answer is 0. - Single nonzero digit (
"7"): the answer is 1. - Valid zeros (
"10","20"): exactly 1 decoding each. - Invalid zeros (
"30","100"):"30"is too large and"00"is never valid, so the answer is 0. - Pairs above 26 (
"27","99"): only the one-digit split works, so the answer is 1. - Long runs of 1s and 2s: the count grows like Fibonacci numbers. A string of 45 ones has 1,836,311,903 decodings, close to the 32-bit limit.
Common Mistakes
- Treating
"0"as a letter: forgetting that a lone zero kills that branch. - Accepting
"07"as a two-digit piece: check that the first digit is'1'or'2', not just that the value is at most 26. - Off-by-one base cases: the empty prefix (or the empty suffix) has exactly one decoding, not zero.
- Plain recursion without a cache: it is exponential and times out on 100 characters.
- Assuming every prefix count fits in 32 bits: a prefix can have more decodings than the whole string, and on a string that turns out to be undecodable the counts can pass even 64 bits before the dead
0is reached. Cap the counts (as the typed versions here do) or use big integers; a wider type alone is not enough.
Interview Tips
- Start by listing the two choices at each index and the rules that make each one legal. Interviewers mostly want to see that you handle zeros correctly.
- Write the memoized recursion first if it is easier for you to reason about, then convert it to the two-variable loop.
- Point out the link to Climbing Stairs: same recurrence, but each term is switched on or off by the digits.
- Trace
"2101"or"1110"out loud. Both exercise the zero rules.
Follow-up Questions
- Decode Ways II (LC 639): the string may contain
'*', meaning any digit from 1 to 9. Each transition then contributes a multiplier, and the answer is taken modulo 1,000,000,007. - List every decoding: use backtracking. The output itself can be exponential in size.
- Different alphabets: if codes go up to some value
K, the two-digit check becomes “between 10 and K”, or with longer codes you look back further than two positions. - Huge answers: without the 32-bit guarantee, return the count modulo a prime, or use big integers.