Start learning free

LESSON 450 OF 540 · DYNAMIC PROGRAMMING

Decode Ways in Go: Dynamic Programming in O(n) Time

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

GO · DYNAMIC PROGRAMMING

Decode Ways in Go, explained

Problem overview

A message of capital letters was turned into digits by writing each letter as its position in the alphabet: A is 1, B is 2, up to Z, which is 26. The function numDecodings receives a string s of digits and returns the number of ways to split it into groups, each a number from 1 to 26, so that every group stands for a letter. A group can't start with 0: "06" is not the same as "6", and no letter is 0. If the string can't be decoded, the answer is 0.

For s = "12" the answer is 2: the groups 1, 2 give AB, and the single group 12 gives L. For s = "226" the answer is 3: 2, 26 gives BZ; 22, 6 gives VF; 2, 2, 6 gives BBF. For s = "06" the answer is 0, because the first group would have to begin with 0.

Approach: count decodings of every beginning

The last group of any decoding is either one digit or two digits. That splits the problem into smaller copies of itself. Let dp[i] be the number of ways to decode the first i digits of s. To decode the first i digits:

If the last digit, s[i-1], is not '0', it can be a letter on its own. Every decoding of the first i - 1 digits, followed by this letter, is a decoding of the first i. That adds 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, followed by it, is a decoding of the first i. That adds dp[i-2].

The two cases never overlap, since one ends in a one-digit group and the other in a two-digit group, so the counts are added. A pair such as 07 starts with 0 and is no letter, and a pair such as 27 is above 26. Neither adds anything.

Trying every split with plain recursion repeats the same suffixes many times, and the work grows exponentially. The table computes each dp[i] once from the two before it, which gives the O(n) time the statement asks for.

For "226" the table, from dp[0] to dp[3], is [1 1 2 3], and for "11106" it is [1 1 2 3 2 2].

Step by step

Store the length in n := len(s).
Create the table dp := make([]int, n+1): n + 1 zeros. dp[0] stands for the empty beginning, before any digit.
Set dp[0] = 1. The empty beginning has exactly one decoding, with no letters. Every longer decoding builds on it, so it must count as one way and not zero.
Handle the first digit. If s[0] != '0', set dp[1] = 1. One digit from 1 to 9 is a letter. If the string starts with 0, dp[1] stays 0, and so does every count built on it.
Loop from 2 to n with for i := 2; i <= n; i++. The entries dp[0] and dp[1] are known, each later one needs the two before it, and the last one, dp[n], covers all of s.
Use the last digit alone. If s[i-1] != '0', add dp[i-1] to dp[i] with +=.
Read the last two digits as a number. two, _ := strconv.Atoi(s[i-2 : i]) converts the slice s[i-2 : i], which holds the characters at i-2 and i-1. Atoi returns the number and an error. The two characters are always digits, so the error is dropped with _.
Use the pair if it is a letter. If two >= 10 && two <= 26, add dp[i-2] to dp[i].
Return dp[n] after the loop.

The solution in Go

func numDecodings(s string) int {
    n := len(s)
    dp := make([]int, n+1)
    dp[0] = 1
    if s[0] != '0' {
        dp[1] = 1
    }
    for i := 2; i <= n; i++ {
        if s[i-1] != '0' {
            dp[i] += dp[i-1]
        }
        two, _ := strconv.Atoi(s[i-2 : i])
        if two >= 10 && two <= 26 {
            dp[i] += dp[i-2]
        }
    }
    return dp[n]
}

The Go details worth knowing:

Indexing a string gives a byte. s[0] has type byte, the numeric code of the character, so it is compared with the character literal '0', in single quotes. Comparing it with the string "0" would not compile. Because the string holds only ASCII digits, one byte is one character.
String slices. s[i-2 : i] is a substring from index i-2 up to, but not including, i. It shares the original's memory, so no copy is made. For "226" and i = 3, it is "26".
strconv.Atoi and leading zeros. Atoi("07") returns 7 with no error, so the range test two >= 10 is what rejects pairs that start with 0. Atoi also accepts a leading + or -, but the characters here are always digits.
The blank identifier. two, _ := ... discards the second return value. Go requires every declared variable to be used, so an error variable you never read would be a compile error.
make([]int, n+1). It creates a slice of n + 1 integers, all 0, ready to use. The += operations rely on those zeros.
Integer size. int is 64 bits, so the counts never overflow for strings of up to 100 digits, and the statement promises the answer fits in 32 bits.

Complexity

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

Space: O(n). The table holds n + 1 integers. Since dp[i] looks only at the two previous entries, two variables would be enough for O(1) space, but the table makes the idea easier to follow.

Edge cases and common mistakes

A leading zero. "06" gives 0 and "0" gives 0. The first digit can't be a letter, and 06 is not a valid pair.
A zero in the middle. "10" gives 1, since the 0 can only be the end of the group 10. "100" gives 0, because the groups would have to be 10 and 0, and 0 is no letter, while 00 isn't a letter either. "30" gives 0, because 30 is above 26 and 0 alone is not a letter.
Pairs above 26. "27" gives 1: only the groups 2 and 7. The pair 27 is not a letter.
A single digit. "1" gives 1. The loop does not run, and dp[1] was set before it.
Counts growing like Fibonacci numbers. "1111111111" (ten 1s) gives 89, and its table is [1 1 2 3 5 8 13 21 34 55 89]. Every pair 11 is a letter, so each entry is the sum of the two before it.
A zero that blocks a path. "2101" gives 1, and "230" gives 0.
Setting dp[0] to 0. Every count would stay 0, because everything builds on the empty beginning.
Using if and else. The one-digit and two-digit cases are independent, and both can add to dp[i]. Two separate if statements are correct.
Forgetting the lower bound 10. Without two >= 10, a pair like 07 would be counted as the letter G with a leading zero.

Testing

s = "12" gives 2.
s = "226" gives 3.
s = "06" gives 0.
s = "11106" gives 2.
s = "10" gives 1.
s = "100" gives 0.
s = "27" gives 1.
s = "2101" gives 1.
s = "1111111111" gives 89.
s = "2611055971756562" gives 4.

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

Start learning free