Decode Ways

MEDIUM✓ CHIP-TIMEDLC #91 — FULL STATEMENT ↗

The drill: Digits 1 through 26 stand in for letters A through Z, and a digit string can split into that alphabet more than one way. Count how many valid decodings a digit string has.

THE BRIEFING — THE FULL DRILL, IN MY OWN WORDS

A string of digits arrives, meant to be decoded back into letters where 1 stands for A up through 26 for Z. Each letter in the original message consumed either one digit or two.

A single digit decodes only when it isn't '0', and a pair of digits decodes only when the two-digit number they form falls between 10 and 26 inclusive — anything outside that range is not a valid letter.

The same digit string can often split into letters more than one way. The task is to count how many distinct valid splits exist, not to produce any one of them.

EX 01

s = "1"

→ 1

MINIMUM SIZE, SINGLE VALID DIGIT

EX 02

s = "10"

→ 1

MUST BE READ AS A PAIR, THE '0' CAN'T STAND ALONE

EX 03

s = "27"

→ 1

PAIR OUT OF RANGE, EACH DIGIT READ ALONE

string length can run into the low hundreds
digits are '0' through '9' only, no other characters
a lone '0' can never start a valid letter on its own
a two-digit letter must fall between 10 and 26 inclusive
answer is the count of distinct valid decodings

THE HINTS — TAKE ONLY WHAT YOU NEED

HINT 1 THE NUDGE

At each position you're really choosing how many digits the next letter eats — one digit or two — but a leading zero and an out-of-range pair both kill a branch instantly. What makes some choices dead ends?

HINT 2 THE STRUCTURE

The number of ways to decode up to position i only depends on how many ways existed one digit back (if this digit alone is valid) and two digits back (if the last two digits form a valid pair).

HINT 3 ONE STEP FROM THE ANSWER

Roll two counts forward: the count ending here adds the one-digit-back count when the current digit isn't '0', and adds the two-digit-back count when the last two digits form 10 through 26.

COACH'S BOARD — THE PATTERN, STEP BY STEP

THE ROLLING SPLITPATTERN · ROLLING SPLIT COUNTs = "226"

WAYS TO DECODE PREFIX

— empty —

STEP 1

Digits '2', '2', '6' — the string doesn't start with '0', so at least one decoding exists. Track ways ending at each prefix length.

STEP 1 / 6 · ← → WORK TOO

THE SPLITS — TWO PACES, TWO LANGUAGES

grind/decode-ways.py — RACE PACE

LANG ▸

PACE ▸

class Solution:
    def numDecodings(self, s: str) -> int:
        n = len(s)
        if s[0] == "0":
            return 0

        prev2, prev1 = 1, 1                          # ways for empty prefix, first digit
        for i in range(1, n):
            cur = 0
            if s[i] != "0":
                cur += prev1
            two = int(s[i - 1:i + 1])
            if 10 <= two <= 26:
                cur += prev2
            prev2, prev1 = prev1, cur
        return prev1

TIME O(N)SPACE O(1)PYTHON · RACE PACE · 16 LN

class Solution:
    def numDecodings(self, s: str) -> int:
        n = len(s)

        def ways(i: int) -> int:
            if i == n:
                return 1
            if s[i] == "0":                        # no letter maps to a leading zero
                return 0
            count = ways(i + 1)                     # take one digit
            if i + 1 < n and int(s[i:i + 2]) <= 26:  # take two digits
                count += ways(i + 2)
            return count

        return ways(0)

TIME O(2^N)SPACE O(N)PYTHON · TRAINING PACE · 15 LN

class Solution {
    public int numDecodings(String s) {
        int n = s.length();
        if (s.charAt(0) == '0') {
            return 0;
        }
        int prev2 = 1, prev1 = 1;
        for (int i = 1; i < n; 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;
    }
}

TIME O(N)SPACE O(1)JAVA · RACE PACE · 22 LN

class Solution {
    public int numDecodings(String s) {
        return ways(s, 0);
    }

    private int ways(String s, int i) {
        int n = s.length();
        if (i == n) {
            return 1;
        }
        if (s.charAt(i) == '0') {
            return 0;
        }
        int count = ways(s, i + 1);
        if (i + 1 < n && Integer.parseInt(s.substring(i, i + 2)) <= 26) {
            count += ways(s, i + 2);
        }
        return count;
    }
}

TIME O(2^N)SPACE O(N)JAVA · TRAINING PACE · 20 LN

✓ CHIP-TIMED — ALL 4 SOLUTIONS RAN GREEN AGAINST SELF-AUTHORED CASES IN CI · JDK 21 · CPYTHON 3.12 · NOTHING PUBLISHES RED