78 · Decode Ways

In an Xcode test target:

import Testing

struct DecodeWaysTests {

    @Test(arguments: [
        ("2611", 4),
        ("10", 1),
        ("06", 0),
    ])
    func countsTheLetterMessagesThatGiveTheseDigits(digits: String, expected: Int) {
        #expect(numDecodings(digits) == expected)
    }

    // MARK: - Privates
    private func numDecodings(_ text: String) -> Int {
        0
    }
}

In a playground:

func numDecodings(_ text: String) -> Int {
    0 // your solution
}

let cases: [(String, Int)] = [
    ("2611", 4),
    ("10", 1),
    ("06", 0),
]
for (digits, expected) in cases {
    let got = numDecodings(digits)
    print(got == expected ? "PASS" : "FAIL", digits, "→", got, "expected", expected)
}

1-D dynamic programming, counting — Climbing Stairs with rules. The cue is "how many ways" to read a sequence where each piece is one or two items long. The last piece of any reading is either the last digit alone or the last two digits together, and those two groups don't overlap. So the count for a prefix is the sum of two smaller counts — exactly Climbing Stairs — except that each move is allowed only when the digits form a valid letter.

Subproblem: the number of ways to read the first i digits. Recurrence: ways for i = (ways for i − 1, if digit i is not 0) + (ways for i − 2, if the two digits ending at i make a number from 10 to 26).

The empty prefix has one reading (nothing), and the first digit has one reading unless it is 0. Then move along the digits. At each one, start from zero: if this digit is 1–9 it can be its own letter, so add the count from one step back; if it and the digit before it form 10–26, they can be one letter, so add the count from two steps back. Only the last two counts are ever needed, so keep two numbers. A 0 that can't pair with the digit before it (as in "30") makes the count 0, and it stays 0 to the end — correct, because nothing after it can repair the message.

Time O(n): constant work per digit. Space O(1) beyond the digit array.

func numDecodings(_ text: String) -> Int {
    let digits = text.compactMap(\.wholeNumberValue)
    guard let first = digits.first else { return 0 }
    var twoBack = 1                            // ways to read the empty prefix
    var oneBack = first == 0 ? 0 : 1           // ways to read the first digit
    for index in digits.indices.dropFirst() {
        var ways = 0
        if digits[index] != 0 { ways += oneBack }                  // one-digit letter
        let pair = digits[index - 1] * 10 + digits[index]
        if digits[index - 1] != 0 && pair <= 26 { ways += twoBack } // two-digit letter, 10–26
        (twoBack, oneBack) = (oneBack, ways)
    }
    return oneBack
}

The two-digit check is two conditions: the first digit isn't 0 (that's what rules out "06") and the value is at most 26. Building the pair with arithmetic instead of parsing a substring is both faster and avoids the trap below.

Verified with swift test on Swift 6.4 in Swift 6 mode: the three examples above, six more ("1", "0", "100", "27", "226", "1201234"), and 3,000 random digit strings rich in 0s, 1s and 2s checked against a brute-force recursion.

"2611"

Answer 4.

"10" — the 1 gives one way. The 0 can't stand alone (+0), but 10 is a letter, so it takes the count from two back, 1. Answer 1.

"06" — the first digit is 0, so one-back starts at 0. The 6 alone adds that 0; the pair starts with 0, so it adds nothing. Answer 0.

Int("06") is 6, so a parsed pair passes a "1 to 26" check. A natural first draft cuts the two characters out and parses them: if let pair = Int(String(letters[index - 1...index])), (1...26).contains(pair). Swift's integer parser accepts leading zeros, so "06" parses to 6, lands in range, and is counted as a letter — the draft returns 1 for "06" instead of 0. (It also accepts a leading +: Int("+6") is 6.) Either write the range as 10...26, or build the number from digits and check that the first digit isn't 0, as the solution does. The parse version also allocates a String for every position.

The surrounding trap is the usual one: text[index] doesn't compile on a String. Converting once — here to [Int] with compactMap(\.wholeNumberValue) — gives integer indexing and digit values in one step.

• "The message may also contain *, which stands for any digit 1–9 (Decode Ways II)." → Same two counts, but each condition becomes a count of matching cases (* alone is 9 ways, 1* is 9, 2* is 6, ** is 15), and the statement asks for the answer modulo 1,000,000,007.
• "Return the decodings, not the count." → Backtracking over the same two choices; the output itself can be exponential, so no DP can make it fast.
• "Why does the count stay 0 after a bad 0?" → The first prefix with no reading always ends in a 0 that couldn't pair with the digit before it. The next digit can't pair with that 0 either (no piece starts with 0), and on its own it only adds the 0 count — so from there both counts stay 0.