Start learning free

LESSON 450 OF 540 · DYNAMIC PROGRAMMING

Decode Ways in Scala: 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

Guided

Ctrl + Enter to check

SCALA · DYNAMIC PROGRAMMING

Decode Ways in Scala, explained

Problem overview

numDecodings receives a string s of digits and returns how many ways it can be split into groups that each read as a number from 1 to 26, where 1 is A, 2 is B and 26 is Z. A group can't start with 0: "06" is not "6", and no letter is 0. If there is no valid split, the answer is 0.

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

Approach: count decodings of each beginning

Trying every split is exponential: each digit may start a new group or join the previous one. But the count for a long beginning of s can be built from the counts of shorter beginnings. Let dp(i) be the number of ways to decode the first i digits. Think of the last group of such a decoding. It is either:

one digit, the digit at position i - 1, which works when it isn't '0'. Every decoding of the first i - 1 digits can be followed by it, so it adds dp(i - 1);
two digits, the digits at positions i - 2 and i - 1, which works when they form a number from 10 to 26. Every decoding of the first i - 2 digits can be followed by it, so it adds dp(i - 2).

The two cases never produce the same decoding, because the last group has a different length, so dp(i) is their sum. The base is dp(0) = 1: the empty beginning has exactly one decoding, with no letters, and every longer decoding is built on it. The answer is dp(n). Each entry takes constant work, so the whole table costs O(n).

Here are the tables the solution builds:

"226"   dp = [1, 1, 2, 3]
"11106" dp = [1, 1, 2, 3, 2, 2]
"100"   dp = [1, 1, 1, 0]
"06"    dp = [1, 0, 0]

For "226", dp(2) = 2 because the first two digits, 22, read as 2, 2 or as 22. Then dp(3) adds dp(2) for the single 6 and dp(1) for the pair 26, giving 2 + 1 = 3. For "11106" the last digit 6 adds dp(4) = 2, and the pair 06 adds nothing, since 06 is below 10. So dp(5) is 2, the two decodings from the problem statement.

Step by step

Store the length: val n = s.length.
Make the table. val dp = Array.fill(n + 1)(0) creates n + 1 zeros: one entry per beginning, plus the empty one at index 0.
Set dp(0) = 1. The empty beginning has one decoding.
The first digit. If s(0) != '0', set dp(1) = 1. A string starting with 0 keeps dp(1) = 0, and every count built on it stays 0 too.
Loop with i <- 2 to n. The first two entries are known, each later one needs the two before it, and to includes n. For a one-digit string the range is empty and the loop doesn't run.
Single digit. If s(i - 1) != '0', add dp(i - 1) to dp(i) with +=.
Read the pair. val two = s.substring(i - 2, i).toInt takes the characters at i - 2 and i - 1 as a number: "26" gives 26, "07" gives 7.
Valid pair. If two >= 10 && two <= 26, add dp(i - 2) to dp(i). A pair below 10 starts with 0, and one above 26 is no letter.
Return dp(n) as the last expression.

The solution in Scala

class Solution {
    def numDecodings(s: String): Int = {
        val n = s.length
        val dp = Array.fill(n + 1)(0)
        dp(0) = 1
        if (s(0) != '0') {
            dp(1) = 1
        }
        for (i <- 2 to 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)
            }
        }
        dp(n)
    }
}

Scala details worth knowing:

Indexing. A string and an array are both indexed with parentheses, s(i - 1) and dp(i). The string gives a Char, which is why it is compared with '0' in single quotes, not "0".
Array.fill(n + 1)(0) builds an array of n + 1 elements, all 0. Arrays are mutable, so dp(i) += dp(i - 1) changes the element in place.
substring(i - 2, i) includes the first index and excludes the second, so it holds exactly two characters. .toInt parses them, and a leading zero is fine: "07".toInt is 7. That is why the check on two uses the lower bound 10 instead of testing for '0'.
Integer size. Int is 32 bits and overflow wraps silently. The lesson guarantees that the answer fits.
No return. The last expression, dp(n), is the result of the method.

Complexity

Time: O(n). The loop runs n - 1 times and each round does a constant amount of work: one character check, one substring of two characters and at most two additions.

Space: O(n). The table has n + 1 entries. Because dp(i) depends only on the two entries before it, two variables could replace the table and bring the space down to O(1).

Edge cases and common mistakes

A leading zero. "06" gives 0: dp(1) stays 0, the 6 adds dp(1), which is 0, and the pair 06 is below 10.
A zero that can't be used. "100" gives 0. The pair 10 is a valid letter, but the last 0 has nothing to join: 00 is no letter and a lone 0 is no letter. Likewise "30" gives 0, since 30 is above 26.
A zero that must join. "10" gives 1, as J. The 0 can't stand alone, so only the pair counts. "110" also gives 1: the only way is 1 and 10.
Pairs above 26. "27" gives 1, only 2 and 7, because 27 is no letter.
Forgetting dp(0) = 1. With 0 there, dp(2) for "12" would miss the pair 12, and every answer would be too small.
Accepting pairs with a leading zero. Parsing "06" gives 6, which looks like a valid letter. The check two >= 10 is what rejects it.
A single digit. "1" gives 1 and "0" gives 0; the loop doesn't run. The string is never empty, so reading s(0) is safe.

Testing

Results from running the solution:

`s`	Result
`"12"`	2
`"226"`	3
`"06"`	0
`"11106"`	2
`"10"`	1
`"100"`	0
`"27"`	1
`"30"`	0
`"110"`	1
`"1123"`	5
`"1"`	1

Keep going with Scala500+ step-by-step lessons, from your first line of code to coding interviews. Free to start.

Start learning free