A warehouse printer encodes SKU letters as digits: A=1 … Z=26. The packing station is handed a digit string and must count how many letter sequences it could mean — not pick one. The intern recursed from index 0: take one digit if it is 1–9, take two if they form 10–26. A three-digit stub returned. A forty-digit tracking code was still splitting when the scanner timed out.

Decode Ways asks how many ways a digit string maps onto letters 1–26. Recursing on every legal split uses that map and still pays an exponential tree. A lone 0 is not a letter. "06" is not 6.

This is an interview writeup, not a knapsack lecture. There is no decode-ways algorithm post to lean on. Here we only care about the count of ways to finish each prefix from a legal one-digit or two-digit tail.

The problem

Given a String s of digits, return the number of ways to decode it. A letter is a substring "1"…"9" or "10"…"26". A leading zero is illegal. Order of letters follows the digits left to right; you may not skip a digit.

s = "12"   →  2    "AB" (1,2) or "L" (12)
s = "226"  →  3    "BBF" (2,2,6), "BZ" (2,26), "VF" (22,6)
s = "10"   →  1    only "J"; "1" then "0" is dead
s = "06"   →  0    leading zero; 6 is not written "06"
s = "0"    →  0

Note: "27" is only "BG". 27 is past Z, so the two-digit take is illegal. "10" and "20" live only as a pair — the trailing 0 cannot stand alone.

Recursing on one digit or two is the honest brute force

From index i, if s.charAt(i) is '0', this prefix is dead. Otherwise take one digit and recurse at i + 1. If the next two characters form 10–26, also recurse at i + 2. Hitting the end is one way. Correct. Exponential without a memo: each index forks up to twice.

int numDecodingsRec(String s) {
    return decodeFrom(s, 0);
}

int decodeFrom(String s, int i) {
    if (i == s.length()) {
        return 1;
    }
    if (s.charAt(i) == '0') {
        return 0;
    }
    int ways = decodeFrom(s, i + 1);
    if (i + 1 < s.length()) {
        int two = (s.charAt(i) - '0') * 10 + (s.charAt(i + 1) - '0');
        if (two >= 10 && two <= 26) {
            ways += decodeFrom(s, i + 2);
        }
    }
    return ways;
}

At n = 8 this is a rounding error. At a long tracking code you paid a split tree for a question a linear pass answers: how many ways already finish just before this index, and is the last letter one legal digit or two? Memoizing decodeFrom(i) is the same recurrence filled on demand. Still not a knapsack lecture.

Let dp[i] be the number of ways to decode the prefix s[0..i). dp[0] = 1 — one way to decode nothing. For each i from 1 through n:

  • If s.charAt(i - 1) is not '0', add dp[i - 1] (last letter is one digit).
  • If i >= 2 and the pair s[i-2..i) is 10–26, add dp[i - 2] (last letter is two digits).

A '0' contributes nothing from the one-digit branch. It survives only when the two-digit branch is "10" or "20". If both branches miss, dp[i] stays 0 and every later landing that needs this prefix dies with it.

Walk "226":

s = 2 2 6
    0 1 2      char indexes
dp[i] = ways to decode s[0..i)

i=0  empty                              dp[0] = 1

i=1  one "2"   '2' ok  +dp[0]=1         "2" = B
     two       n/a
                                        dp[1] = 1

i=2  one "2"   '2' ok  +dp[1]=1         "2|2" = BB
     two "22"  22 in 10..26  +dp[0]=1   "22" = V
                                        dp[2] = 2

i=3  one "6"   '6' ok  +dp[2]=2         "2|2|6" = BBF, "22|6" = VF
     two "26"  26 in 10..26  +dp[1]=1   "2|26" = BZ
                                        dp[3] = 3

The Java is that walk. two >= 10 rejects a leading zero ("06" is 6, not in range):

int numDecodings(String s) {
    int n = s.length();
    int[] dp = new int[n + 1];
    dp[0] = 1;
    for (int i = 1; i <= n; i++) {
        if (s.charAt(i - 1) != '0') {
            dp[i] += dp[i - 1];
        }
        if (i >= 2) {
            int two = (s.charAt(i - 2) - '0') * 10 + (s.charAt(i - 1) - '0');
            if (two >= 10 && two <= 26) {
                dp[i] += dp[i - 2];
            }
        }
    }
    return dp[n];
}

Time is O(n) — one pass, constant work per index. Space is O(n) for the array; two rolling integers are enough if they ask.

Note: Do not treat a leading zero as the integer value. "06" is not letter F. "10" is one way, not two. "100" is zero: "10" then "0" is dead, and "1" then "00" never forms a letter.

What interviewers usually poke next

  • Two rolling variables. You only read dp[i-1] and dp[i-2]. Keep prev2 / prev1 and shift. Same recurrence, O(1) extra space.
  • Climbing-stairs shape. Ways to reach i from i-1 or i-2, except each step is gated by digit legality. Same sibling idea; a zero can close one or both doors. Do not switch prompts.
  • Return the strings, not the count. Then you actually emit the splits. The int pass does not remember letters. Say so and stop unless they switch.
  • Stars / Decode Ways II. * as 1–9 or 10–26 wildcards. Different branching. Do not stretch this loop.
  • Overflow. All-ones input grows like Fibonacci. Interview n may fit in int; a longer code needs long. Ask.
  • Empty string. Prompts usually give length ≥ 1. dp[0] = 1 is the empty-prefix seed, not a claim about empty input.

You are done with this problem when you can walk "226" to 3 on a whiteboard, kill "06" and "0" without a special case, and say out loud why the split tree is correct and why a linear landing count is the same numbers.