Decode Ways
Digits encode letters using 1=A through 26=Z. Count the ways to decode the entire string. A code cannot begin with zero.
Work through the cases
3 examplesInput notation
A nonempty digit string of at most 40 characters.Expected result
The number of valid decodings.Case 1
Input
226
Expected output
3
Case 2
Input
06
Expected output
0
Case 3
Input
10
Expected output
1
These notes use simplified input/output notation. The linked platform defines the method signature and judge format.
FROM IDEA TO IMPLEMENTATION
Understand the approach.
Compare the documented approaches below. Brute force, better, and optimal versions appear where available; a direct exercise may need only one approach.
The first idea is recursion: at index i, decode s[i] alone (if not 0), or pair it with the previous digit into 10– 26. n ≤ 100, but without memoization the tree is exponential because the same prefix is decoded again and again. The bottleneck is that the number of ways to decode the first i characters depends only on shorter prefixes, and a valid split is only “one digit / two digits”. That is climbing stairs with encoding constraints. So let f[i] be the number of ways for the first i characters. The empty string has one way; 0 cannot stand alone; only 10– 26 can be a pair. Scan once instead of enumerating every partition.
We define f[i] to represent the number of decoding methods for the first i characters of the string. Initially, f[0]=1, and the rest f[i]=0.
Consider how f[i] transitions.
- If the ith character (i.e., s[i-1]) forms a code on its own, it corresponds to one decoding method, i.e., f[i]=f[i-1]. The premise is s[i-1] \neq 0. - If the string formed by the i-1th character and the ith character is within the range [1,26], then they can be treated as a whole, corresponding to one decoding method, i.e., f[i] = f[i] + f[i-2]. The premise is s[i-2] \neq 0, and s[i-2]s[i-1] is within the range [1,26].
The time complexity is O(n), and the space complexity is O(n). Here, n is the length of the string.
class Solution {
public int numDecodings(String s) {
int n = s.length();
int[] f = new int[n + 1];
f[0] = 1;
for (int i = 1; i <= n; ++i) {
if (s.charAt(i - 1) != '0') {
f[i] = f[i - 1];
}
if (i > 1 && s.charAt(i - 2) != '0' && Integer.valueOf(s.substring(i - 2, i)) <= 26) {
f[i] += f[i - 2];
}
}
return f[n];
}
}Reference code. Platform solutions may use supplied node types, imports, or collection libraries; foundational examples are complete programs.
Solutions adapted from Doocs / LeetCode contributors, licensed under CC BY-SA 4.0. Formatting changed; TypeScript versions converted to JavaScript. Supplemental implementations and approach notes added. Adapted solution material is available under the same license.