#91 Decode Ways
the problem
In plain words
Letters map to numbers: A = 1, …, Z = 26. Given a digit string, count how many ways it can be decoded back into letters. "06" is not valid (no letter is written with a leading zero).
in s = "12"
out 2
"AB" (1 2) or "L" (12).
in s = "226"
out 3
2 2 6, 22 6, 2 26.
in s = "06"
out 0
- 1 ≤ s.length ≤ 100
- s contains only digits, possibly with leading zeros
- The answer fits in a 32-bit int
your turn
Try it before you peek
Read the examples, say the brute force out loud, then write code: here or on LeetCode ↗. Stuck for 20 minutes? Open one hint at a time.
Solve it in the browser
LeetCode-style: complete the class. Compiled by the real javac (Java 17) and judged right here — nothing is sent anywhere.
Solutions are hidden so you can try first. Even 20 minutes of real effort makes the answer stick far better than reading it.
Marking the problem solved, or opening every hint, also shows it.
the aha
Key insight
pattern1D DP
The last letter used either 1 digit (must be 1–9) or 2 digits (must be 10–26). ways(i) = [one-digit ok] · ways(i−1) + [two-digit ok] · ways(i−2).
solutions
From brute force to optimal
From index i, take one digit or two digits.
- End of string → 1.
- '0' at i → 0.
- Add the two-digit branch if ≤ 26.
Up to two branches per position.
Recursion depth.
class Solution { public int numDecodings(String s) { return ways(s, 0); } /** Ways to decode s[i..]. */ private int ways(String s, int i) { if (i == s.length()) return 1; // decoded everything: one complete way if (s.charAt(i) == '0') return 0; // no letter starts with 0 int count = ways(s, i + 1); // take one digit (1..9) if (i + 1 < s.length() && Integer.parseInt(s.substring(i, i + 2)) <= 26) { count += ways(s, i + 2); // take two digits (10..26) } return count; }}ways(i) depends only on i.
- memo filled with −1 (0 is a valid count).
n states.
Memo + stack.
class Solution { public int numDecodings(String s) { int[] memo = new int[s.length()]; Arrays.fill(memo, -1); return ways(s, 0, memo); } private int ways(String s, int i, int[] memo) { if (i == s.length()) return 1; if (s.charAt(i) == '0') return 0; if (memo[i] != -1) return memo[i]; int count = ways(s, i + 1, memo); if (i + 1 < s.length() && Integer.parseInt(s.substring(i, i + 2)) <= 26) count += ways(s, i + 2, memo); return memo[i] = count; }}dp[i] = ways to decode the first i characters.
- dp[0] = 1.
- Add dp[i−1] if s[i−1] ≠ '0'.
- Add dp[i−2] if s[i−2..i−1] is 10..26.
One pass.
The table.
class Solution { public int numDecodings(String s) { int n = s.length(); int[] dp = new int[n + 1]; // dp[i] = ways to decode the first i chars dp[0] = 1; // empty prefix: one (empty) decoding for (int i = 1; i <= n; i++) { if (s.charAt(i - 1) != '0') dp[i] += dp[i - 1]; // last letter used 1 digit if (i >= 2) { int two = Integer.parseInt(s.substring(i - 2, i)); if (two >= 10 && two <= 26) dp[i] += dp[i - 2]; // last letter used 2 digits } } return dp[n]; }}Only dp[i−1] and dp[i−2] are read.
- prev1 = 1 (empty prefix), prev2 = 0.
- Compute cur, shift.
One pass.
Two ints.
class Solution { public int numDecodings(String s) { int prev2 = 0, prev1 = 1; // dp[i-2], dp[i-1]; start: dp[-1] unused, dp[0] = 1 for (int i = 1; i <= s.length(); i++) { int cur = 0; if (s.charAt(i - 1) != '0') cur += prev1; // last letter used one digit (1..9) if (i >= 2) { int two = (s.charAt(i - 2) - '0') * 10 + (s.charAt(i - 1) - '0'); if (two >= 10 && two <= 26) cur += prev2; // last letter used two digits (10..26) } prev2 = prev1; prev1 = cur; } return prev1; }}One digit or two, prefix by prefix
in the room
How to say it in the interview
talk track
- Walk through zeros explicitly: "10" → 1, "100" → 0, "06" → 0. That's where the interviewer will probe.
traps
- Accepting "06" as a two-digit code — two-digit codes must be 10..26.
- Returning 1 for an all-zero string.
what they ask next
Follow-ups
Decode Ways II (LC 639) with '*' wildcards?
Same DP; each position contributes a multiplier (e.g. '*' = 9 one-digit options). Use long and mod 10⁹ + 7.
before you submit
Edge cases to test
- "0" or anything starting with '0' → 0.
- "10" → 1 and "100" → 0: a 0 must pair with the 1 or 2 right before it.
- "27" → 1: 27 is not a letter.
- 45 ones → 1,836,311,903: Fibonacci again, still an int.
practise next
Similar problems
- #70Climbing StairsEasyin Dynamic Programming
- #139Word BreakMediumin Dynamic Programming