Let’s assume that we have "A" assigned as 1, "B" as 2, ..., "Z" as 26. So given a digit-encoded message, such as "123", that could be decoded in several ways: "ABC" (1 2 3), "LC" (12 3), or "AW" (1 23). So the message "123" has 3 ways of being decoded. Let’s use dynamic programming to solve this problem.
To get started, we need to build an array dp[] of size n + 1 to store the decoding count. The count dp[i] will be the count of decoding for the sequence from index 1 to i.
First, we initialize dp[0] = 1 since there’s only one way to decode a sequence of length 0, and dp[1] = 1, because there’s only one way to decode a sequence of length 1.
From here, we start a for loop from 2 to n (length of the digit), and for each index i, we check two things:
(a) If the last digit is not 0, then there could be ways associated with the last digit, we increment count dp[i] = dp[i-1] (b) If second last or last two digits form a number less than or equal to 26, then we increment dp[i] += dp[i-2]
So the pseudo code will look like:
def count_decoding(digits, n):
dp = [0] * (n+1)
dp[0] = 1
dp[1] = 1
for i in range(2, n+1):
if digits[i-1] > '0':
dp[i] = dp[i-1]
if (digits[i-2] == '1' or (digits[i-2] == '2' and digits[i-1] < '7')):
dp[i] += dp[i-2]
return dp[n]With this, you can calculate the number of ways a sequence can be decoded.
For instance, let’s take "1234" as an example:
1. i = 2, "1234" -> last digit is ’2’ and 12 is between 1 to 26, so dp[2] = dp[1] + dp[0] = 2
2. i = 3, "1234" -> last digit is ’3’ and 23 is between 1 to 26, so dp[3] = dp[2] + dp[1] = 3
3. i = 4, "1234" -> last digit is ’4’ but 34 is not between 1 to 26, so dp[4] = dp[3] = 3.
So there are 3 ways to decode the message "1234".
Finally, dp[n] returns the total number of ways the given sequence can be decoded.