Start learning free

LESSON 450 OF 540 · DYNAMIC PROGRAMMING

Decode Ways in Kotlin: Dynamic Programming in O(n)

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 9
    Ctrl + Enter to check

    KOTLIN · DYNAMIC PROGRAMMING

    Decode Ways in Kotlin, explained

    Problem overview

    A message of capital letters was turned into digits: A is 1, B is 2, and so on up to Z, which is 26. To decode a digit string, you split it into groups, each a number from 1 to 26, and replace each group with its letter. A group can't start with 0: "06" is not 6, and no letter is 0. numDecodings(s) returns the number of different ways to decode s, or 0 when there is none.

    The string "12" has 2 decodings: AB (1, 2) and L (12). The string "226" has 3: BZ (2, 26), VF (22, 6) and BBF (2, 2, 6). The string "06" has none, because the first group would start with 0.

    Approach

    Look at the last group of a decoding of the first i digits. It is either the single digit s[i - 1] or the two digits s[i - 2] and s[i - 1]. That gives a recurrence over prefixes of the string. Let dp[i] be the number of ways to decode the first i digits. Then:

    • If the last digit is not 0, it can be a letter on its own. Every decoding of the first i - 1 digits extends with it, so add dp[i - 1].
    • If the last two digits form a number from 10 to 26, they can be one letter. Every decoding of the first i - 2 digits extends with it, so add dp[i - 2]. A pair below 10, such as 07, starts with 0 and is not a letter, and a pair above 26 is not a letter either.

    The two cases are independent, and both can apply, which is why the code adds to dp[i] instead of choosing. Without the table, plain recursion would solve the same prefixes again and again and take exponential time. The table solves each prefix once.

    The base case is dp[0] = 1: the empty beginning has exactly one decoding, the one with no letters. Every longer decoding is built on top of it, so it must count as one way, not zero.

    Step by step

    1. Length. Store s.length in val n.
    2. The table. Create val dp = IntArray(n + 1), one more entry than digits, because dp[0] stands for "no digits yet". All entries start at 0.
    3. Empty prefix. Set dp[0] = 1.
    4. First digit. If s[0] isn't '0', set dp[1] = 1. A string starting with 0 keeps dp[1] = 0, and everything built on it stays 0 too.
    5. Fill the rest with a loop over 2..n. Both dp[0] and dp[1] are known, and each later entry needs the two before it.
    6. Single digit. If s[i - 1] isn't '0', do dp[i] += dp[i - 1].
    7. Pair. Take s.substring(i - 2, i).toInt() into val two, and if two is between 10 and 26, do dp[i] += dp[i - 2].
    8. Answer. Return dp[n].

    The solution in Kotlin

    class Solution {
    fun numDecodings(s: String): Int {
        val n = s.length
        val dp = IntArray(n + 1)
        dp[0] = 1
        if (s[0] != '0') {
            dp[1] = 1
        }
        for (i in 2..n) {
            if (s[i - 1] != '0') {
                dp[i] += dp[i - 1]
            }
            val two = s.substring(i - 2, i).toInt()
            if (two >= 10 && two <= 26) {
                dp[i] += dp[i - 2]
            }
        }
        return dp[n]
    }
}

    Kotlin details worth knowing

    • '0' is a Char. s[0] gives a Char, which is compared with the character '0' in single quotes. The comparison s[0] != '0' is about the character, not the number zero.
    • substring(i - 2, i). The start index is included and the end index is excluded, so it holds the characters at positions i - 2 and i - 1. toInt() then parses it: "26".toInt() is 26, and "07".toInt() is 7, which fails the test two >= 10.
    • 2..n is inclusive. The loop reaches i == n, the whole string. For n == 1 the range 2..1 is empty, so a one-digit string skips the loop, and dp[1] is already set.
    • IntArray(n + 1) creates an array of n + 1 zeros. val only keeps the name tied to the same array; its entries can still change, so dp[i] += ... is fine.
    • Int overflow. Int is 32 bits and wraps silently. The lesson guarantees the answer fits, so it is safe here. For a string of 45 ones the result is 1836311903, but 46 ones would need more than an Int holds and the same code returns -1323752223.
    • An empty string is not allowed. s[0] throws for an empty string. The lesson's constraints promise at least one digit.

    Complexity

    • Time: O(n). The loop runs about n times, and each round does a few comparisons, one substring of two characters and at most two additions.
    • Space: O(n) for the dp table. Each entry needs only the two before it, so two variables could replace the array, but the table is clearer for a first solution.

    Edge cases and common mistakes

    • Leading zero. "06" gives 0. The first digit is 0, so dp[1] stays 0, and the pair 06 is below 10, so nothing is added at i = 2.
    • A zero in the middle. "100" gives 0: the last 0 can't stand alone, and 00 is not a pair in range. "10" gives 1: only the group 10 works, and "30" gives 0 because 30 is too big and 0 can't stand alone.
    • Pairs above 26. "27" gives 1, because only 2 and 7 work as separate letters.
    • Treating a pair like "06" as 6. Taking the number alone, "06".toInt() is 6, which seems fine. The check two >= 10 is what rejects it.
    • Forgetting dp[0] = 1. Setting it to 0 makes every answer 0, since all counts are built from it.
    • Using = instead of +=. Both cases can apply at once, and the second one would erase the first.

    Testing

    The table shows the dp array the solution builds, which makes each result easy to follow:

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