85. Decode Ways

Define dp[i] = number of ways to decode the prefix s[:i]. The very last decoded letter consumes either one digit ('1'..'9') — contributing dp[i-1] ways — or two digits ('10'..'26') — contributing dp[i-2]. Add the valid contributions. Like Fibonacci, only the last two states matter, so two scalars suffice.

The recurrence

For each new position i:

• If s[i] is between '1' and '9' (i.e. not '0'), it can stand alone as a letter 'A'..'I' etc. → add dp[i-1].
• If s[i-1..i+1] (the two-character substring ending at i) is between '10' and '26', it can pair with the previous digit → add dp[i-2].

Otherwise that path contributes 0.

Steps

1. Empty / leading zero: if s is empty or s[0] == '0', return 0. (You can't start with '0' — there's no letter for it.)
2. Initialise prev2 = 1 (decoding empty prefix has 1 way) and prev1 = 1 (decoding length-1 prefix has 1 way, given it's not '0').
3. For i from 1 to len(s) - 1:
   • Start cur = 0.
   • If s[i] != '0', add prev1 to cur.
   • Compute two = int(s[i-1:i+1]). If 10 <= two <= 26, add prev2 to cur.
   • Roll: prev2, prev1 = prev1, cur.
4. Return prev1.

Walk-through

s = "226". Length 3.

Return prev1 = 3. The three decodings are BZ (2-26), BBF (2-2-6), VF (22-6). ✓

Another example, s = "06":

s[0] == '0' → return 0. ✓

s = "12":

Return 2: AB, L. ✓

Why we initialise prev2 = prev1 = 1

Think of dp[0] (ways to decode empty prefix) = 1 (the trivial empty decoding). And dp[1] (assuming valid first char) = 1. The recurrence then matches Fibonacci-like sums.

Edge cases

• s = "0": return 0.
• Embedded '0': e.g. "10" → 1 way (J); "100" → 0 ways ('00' is invalid as a pair, and '0' alone is invalid). The recurrence handles this naturally — both contributions are 0.
• Two-digit > 26: doesn't contribute via the pair branch.

Complexity

• Time: O(n) — one pass.
• Space: O(1) — two scalars.

class Solution {
    public int numDecodings(String s) {
        if (s.isEmpty() || s.charAt(0) == '0') return 0;
        int prev2 = 1, prev1 = 1;
        for (int i = 1; i < s.length(); i++) {
            int cur = 0;
            if (s.charAt(i) != '0') cur += prev1;
            int two = Integer.parseInt(s.substring(i - 1, i + 1));
            if (two >= 10 && two <= 26) cur += prev2;
            prev2 = prev1;
            prev1 = cur;
        }
        return prev1;
    }
}