Start learning free

LESSON 451 OF 541 · DYNAMIC PROGRAMMING

Decode Ways in Swift: O(n) Dynamic Programming

Practice O(n) Read the full explanation

A message made of the capital letters A to Z was turned into digits by writing each letter as its position in the alphabet: A becomes 1, B becomes 2, and so on up to Z, which becomes 26.

To decode the digits, split them into groups, each group a number from 1 to 26, and turn each group back into its letter. A group can't start with 0: "06" is not the same as "6", and no letter is 0. For example, "11106" can be decoded in two ways:

  • "AAJF", from the groups 1, 1, 10, 6;
  • "KJF", from the groups 11, 10, 6.

The groups 1, 11, 06 don't work, because 06 starts with 0.

Given a string s of digits, return the number of ways to decode it. If it can't be decoded at all, return 0.

Example 1:

Input: s = "12"
Output: 2
Explanation: "12" can be decoded as "AB" (1, 2) or as "L" (12).

Example 2:

Input: s = "226"
Output: 3
Explanation: "226" can be decoded as "BZ" (2, 26), "VF" (22, 6) or "BBF" (2, 2, 6).

Example 3:

Input: s = "06"
Output: 0
Explanation: The first group would have to start with 0: "0" is no letter, and "06" can't be read as 6. So "06" can't be decoded.

Constraints:

  • 1 <= s.length <= 100
  • s is made of digits only, 0 to 9, and may start with 0.
  • The answer fits in a 32-bit integer.

Note:

Your algorithm should run in O(n) time, where n is the length of s.

STEP 1 OF 10
    Ctrl + Enter to check

    SWIFT · DYNAMIC PROGRAMMING

    Decode Ways in Swift, explained

    Problem overview

    numDecodings receives a string s of digits and returns how many ways it can be split into groups that are each a number from 1 to 26, where 1 is A, 2 is B, up to 26 for Z. A group can't start with 0, so "06" isn't a 6. If no split works, the answer is 0.

    For "12" the answer is 2: the groups 1, 2 (AB) or the single group 12 (L). For "226" it is 3: 2, 26 or 22, 6 or 2, 2, 6. For "06" it is 0, because the first group would start with 0.

    Approach: count decodings of every beginning

    Let dp[i] be the number of ways to decode the first i digits. The last group of any decoding of those digits is either one digit or two:

    • If digit i isn't 0, it can be a letter alone, and every decoding of the first i - 1 digits extends with it: add dp[i - 1].
    • If digits i - 1 and i together make a number from 10 to 26, they can be one letter, and every decoding of the first i - 2 digits extends with it: add dp[i - 2].

    Pairs below 10 (such as 07) start with 0 and are no letter, and pairs above 26 don't exist as letters. A 0 can therefore only be used as the second digit of 10 or 20.

    The base case is dp[0] = 1: the empty beginning has exactly one decoding, the empty one. Without it, no longer count could be built. Each entry needs only the two before it, so one pass is enough.

    For "226" the table is:

    dp = [1, 1, 2, 3]

    The entry for the first digit is 1, for 22 it is 2 (2, 2 or 22), and for 226 it is 3. For "11106" the table is [1, 1, 2, 3, 2, 2], ending in 2: AAJF and KJF.

    Step by step

    1. Get the characters. A Swift String can't be indexed with a number, so Array(s) copies its characters into chars.
    2. Count them into n.
    3. Create the table. dp is [Int](repeating: 0, count: n + 1): one entry more than digits, where entry 0 stands for the empty beginning.
    4. Base case. Set dp[0] to 1.
    5. First digit. If chars[0] isn't "0", set dp[1] to 1. A string starting with 0 leaves it at 0, and every count built on it stays 0.
    6. Loop i over 2..<n + 1, so the last value is n.
    7. One-digit group. If chars[i - 1] isn't "0", add dp[i - 1] to dp[i].
    8. Two-digit number. Compute two from the digits at i - 2 and i - 1: the first times 10 plus the second, each taken with wholeNumberValue!.
    9. Two-digit group. If two is between 10 and 26, add dp[i - 2] to dp[i].
    10. Return dp[n].

    The solution in Swift

    class Solution {
    func numDecodings(_ s: String) -> Int {
        let chars = Array(s)
        let n = chars.count
        var dp = [Int](repeating: 0, count: n + 1)
        dp[0] = 1
        if chars[0] != "0" {
            dp[1] = 1
        }
        for i in 2..<n + 1 {
            if chars[i - 1] != "0" {
                dp[i] += dp[i - 1]
            }
            let two = chars[i - 2].wholeNumberValue! * 10 + chars[i - 1].wholeNumberValue!
            if two >= 10 && two <= 26 {
                dp[i] += dp[i - 2]
            }
        }
        return dp[n]
    }
}

    The Swift details worth a closer look:

    • Strings have no integer subscript. Writing s[1] on a String doesn't compile: the error is "cannot subscript String with an Int, use a String.Index instead". Array(s) makes an array of Character values, which can be indexed by position, and chars.count is the number of characters.
    • Comparing with a literal. chars[i - 1] != "0" compares a Character with the literal "0", which Swift reads as a Character here.
    • wholeNumberValue. It is a property of Character that returns an Int?: the value of a digit, or nil for a character that isn't one. The input here is digits only, so ! never fails. For the characters "2" and "6", two is 26, and for "0" and "7" it is 7.
    • Operator precedence. In 2..<n + 1, the addition happens first, so the range is 2..<(n + 1). For n == 1 it is 2..<2, which is empty and fine. A range whose lower bound is above its upper bound, such as 2..<1, would crash.
    • Table of Int. Int is 64 bits in Swift, and overflow crashes the program instead of wrapping. The lesson's answers fit in 32 bits, so there is no risk here.

    Complexity

    Time: O(n). Each of the n entries needs a constant amount of work, and copying the characters is O(n) as well.

    Space: O(n). The table and the character array each hold about n entries. Since dp[i] only reads the two entries before it, two variables would be enough, but the table is easier to read.

    Edge cases and common mistakes

    • Leading zero. "06" and "0" both give 0.
    • A zero in the middle. "10" gives 1 (only the group 10), and "100" gives 0: the last 0 can't stand alone, and 00 is not a letter, so no split works. "30" also gives 0, because 30 is above 26.
    • Numbers above 26. "27" gives 1: only 2 and 7. "12" gives 2.
    • A single digit. "1" gives 1. The loop doesn't run, and the answer comes from dp[1].
    • Treating a 0 as a digit-by-digit letter. Adding dp[i - 1] for a 0 would count a letter that doesn't exist.
    • Using two >= 1 instead of two >= 10. A pair such as 07 would count as the number 7, but a group can't start with 0.
    • Starting with dp[0] = 0. Every count would stay 0.

    Testing

    • "12" gives 2.
    • "226" gives 3.
    • "06" gives 0.
    • "11106" gives 2.
    • "0" gives 0, and "1" gives 1.
    • "10" gives 1, and "100" gives 0.
    • "27" gives 1, and "30" gives 0.
    • "2101" gives 1.
    Keep going with Swift500+ step-by-step lessons, from your first line of code to coding interviews. Free to start.
    Start learning free