Count decodings of a given sequence of digits
Given a positive number, map its digits to the corresponding alphabet in the mapping table [(1, 'A'), (2, 'B'), … (26, 'Z')], and return the count of the total number of decodings possible. Assume that the input number can be split into valid single-digit or two-digit numbers that are present in the mapping table.
For example,
Output: 3
The possible decodings are [ABC, AW, LC]
Input: 1221
Output: 5
The possible decodings are [ABBA, ABU, AVA, LBA, LU]
From the above examples, it is evident that,
- A single-digit between
1–9can be mapped to a corresponding alphabet betweenA–I. - Two digits between
10–26can be mapped to a corresponding alphabet betweenJ–Z.
So, the problem of computing T(n) for an n–digit number can be broken down into the subproblems of computing T(n-1) if the last digit lies between 1–9 and computing T(n-2) if the last two digits lie between 10–26, and finally adding the two.
The algorithm can be implemented as follows in C++, Java, and Python:
C++
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 |
#include <iostream> #include <string> using namespace std; // Function to count the total decodings of a given sequence of digits int count(string seq, int n) { // base case if (n == 0 || n == 1) { return 1; } int sum = 0; // consider single-digit numbers (1, 2, … 8, 9) if (seq[n - 1] >= '1' && seq[n - 1] <= '9') { sum = count(seq, n - 1); } // consider 2-digit numbers (10, 11, … 19, 20, … 25, 26) if (seq[n - 2] == '1' || (seq[n - 2] == '2' && seq[n - 1] <= '6')) { sum += count(seq, n - 2); } return sum; } int main() { int x = 1221; string seq = to_string(x); cout << "The total number of decodings are " << count(seq, seq.length()) << endl; return 0; } |
Output:
The total number of decodings are 5
Java
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 |
class Main { // Function to count the total decodings of a given sequence of digits public static int count(char[] seq, int n) { // base case if (n == 0 || n == 1) { return 1; } int sum = 0; // consider single-digit numbers (1, 2, … 8, 9) if (seq[n - 1] >= '1' && seq[n - 1] <= '9') { sum = count(seq, n - 1); } // consider 2-digit numbers (10, 11, … 19, 20, … 25, 26) if (seq[n - 2] == '1' || (seq[n - 2] == '2' && seq[n - 1] <= '6')) { sum += count(seq, n - 2); } return sum; } public static void main(String[] args) { int x = 1221; char[] chars = String.valueOf(x).toCharArray(); System.out.println("The total number of decodings are " + count(chars, chars.length)); } } |
Output:
The total number of decodings are 5
Python
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 |
# Function to count the total decodings of a given sequence of digits def count(seq, n): # base case if n == 0 or n == 1: return 1 total = 0 # consider single-digit numbers (1, 2, … 8, 9) if '1' <= seq[n - 1] <= '9': total = count(seq, n - 1) # consider 2-digit numbers (10, 11, … 19, 20, … 25, 26) if seq[n - 2] == '1' or (seq[n - 2] == '2' and seq[n - 1] <= '6'): total += count(seq, n - 2) return total if __name__ == '__main__': x = 1221 seq = str(x) print('The total number of decodings are', count(seq, len(seq))) |
Output:
The total number of decodings are 5
The time complexity of the above solution is exponential as several subproblems are recalculated repeatedly. It also requires extra space for the recursion (call stack).
If we take a closer look at the solution, the value of T(n) can be calculated in constant time if the values of T(n-1) and T(n-2) are known in advance. The idea is to solve the smaller subproblems first and then solve the larger subproblems using the already computed results of the smaller subproblems. This approach is also known as the bottom-up approach and used to solve dynamic programming problems.
Following is the dynamic programming solution in C++, Java, and Python, where solutions to the subproblems are derived in a bottom-up manner:
C++
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 |
#include <iostream> #include <string> using namespace std; // Function to count the total decodings of a given sequence of digits int count(int x) { // convert `x` to a string string seq = to_string(x); int n = seq.length(); // create an auxiliary array to store results to the subproblems int T[n + 1] = { 0 }; // base case T[0] = 1; T[1] = 1; // fill the auxiliary array `T[]` in a bottom-up manner for (int i = 2; i <= n; i++) { // consider single-digit numbers (1, 2, … 8, 9) if (seq[i - 1] > '0') { T[i] = T[i - 1]; } // consider 2-digit numbers (10, 11, … 19, 20, … 25, 26) if (seq[i - 2] == '1' || (seq[i - 2] == '2' && seq[i - 1] <= '6')) { T[i] += T[i - 2]; } } // last element in the auxiliary array stores the result return T[n]; } int main() { int x = 1221; cout << "The total number of decodings are " << count(x) << endl; return 0; } |
Output:
The total number of decodings are 5
Java
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 |
class Main { // Function to count the total decodings of a given sequence of digits public static int count(int x) { // convert `x` to a string String seq = String.valueOf(x); // create an auxiliary array to store results to the subproblems int[] T = new int[seq.length() + 1]; // base case T[0] = 1; T[1] = 1; // fill the auxiliary array `T[]` in a bottom-up manner for (int i = 2; i <= seq.length(); i++) { // consider single-digit numbers (1, 2, … 8, 9) if (seq.charAt(i - 1) > '0') { T[i] = T[i - 1]; } // consider 2-digit numbers (10, 11, … 19, 20, … 25, 26) if (seq.charAt(i - 2) == '1' || (seq.charAt(i - 2) == '2' && seq.charAt(i - 1) <= '6')) { T[i] += T[i - 2]; } } // last element in the auxiliary array stores the result return T[seq.length()]; } public static void main(String[] args) { int x = 1221; System.out.println("The total number of decodings are " + count(x)); } } |
Output:
The total number of decodings are 5
Python
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 |
# Function to count the total decodings of a given sequence of digits def count(x): # convert `x` to a string seq = str(x) # create an auxiliary array to store results to the subproblems T = [0] * (len(seq) + 1) # base case T[0] = 1 T[1] = 1 # fill the auxiliary array `T` in a bottom-up manner for i in range(2, len(seq) + 1): # consider single-digit numbers (1, 2, … 8, 9) if seq[i - 1] > '0': T[i] = T[i - 1] # consider 2-digit numbers (10, 11, … 19, 20, … 25, 26) if seq[i - 2] == '1' or (seq[i - 2] == '2' and seq[i - 1] <= '6'): T[i] += T[i - 2] # last element in the auxiliary array stores the result return T[-1] if __name__ == '__main__': x = 1221 print('The total number of decodings are', count(x)) |
Output:
The total number of decodings are 5
The time complexity of the above dynamic programming solution is O(n), where n is the length of the input sequence. The extra space used by the program is O(n) for the auxiliary array.
However, the code only reads the last two elements from the auxiliary array at any point. Therefore, the space complexity can be further reduced to O(1) by keeping track of the solutions to only the last two subproblems. This approach is demonstrated below in C++, Java, and Python:
C++
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 |
#include <iostream> #include <string> using namespace std; // Function to count the total decodings of a given sequence of digits int count(int x) { string seq = to_string(x); // convert `x` to a sequence of digits // keep track of the results of only the last two subproblems int prev_of_prev = 1; int prev = 1; for (int i = 2; i <= seq.length(); i++) { int curr = 0; // consider single-digit numbers (1, 2, … 8, 9) if (seq[i - 1] > '0') { curr = prev; } // consider 2-digit numbers (10, 11, … 19, 20, … 25, 26) if (seq[i - 2] == '1' || (seq[i - 2] == '2' && seq[i - 1] <= '6')) { curr += prev_of_prev; } prev_of_prev = prev; prev = curr; } return prev; } int main() { int x = 1221; cout << "The total number of decodings are " << count(x) << endl; return 0; } |
Output:
The total number of decodings are 5
Java
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 |
class Main { // Function to count the total decodings of a given sequence of digits public static int count(int x) { // convert `x` to a sequence of digits char[] chars = String.valueOf(x).toCharArray(); // keep track of the results of only the last two subproblems int prev_of_prev = 1; int prev = 1; for (int i = 2; i <= chars.length; i++) { int curr = 0; // consider single-digit numbers (1, 2, … 8, 9) if (chars[i - 1] > '0') { curr = prev; } // consider 2-digit numbers (10, 11, … 19, 20, … 25, 26) if (chars[i - 2] == '1' || (chars[i - 2] == '2' && chars[i - 1] <= '6')) { curr += prev_of_prev; } prev_of_prev = prev; prev = curr; } return prev; } public static void main(String[] args) { int x = 1221; System.out.println("The total number of decodings are " + count(x)); } } |
Output:
The total number of decodings are 5
Python
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 |
# Function to count the total decodings of a given sequence of digits def count(x): seq = str(x) # convert `x` to a sequence of digits # keep track of the results of only the last two subproblems prev_of_prev = 1 prev = 1 for i in range(2, len(seq) + 1): curr = 0 # consider single-digit numbers (1, 2, … 8, 9) if seq[i - 1] > '0': curr = prev # consider 2-digit numbers (10, 11, … 19, 20, … 25, 26) if seq[i - 2] == '1' or (seq[i - 2] == '2' and seq[i - 1] <= '6'): curr += prev_of_prev prev_of_prev = prev prev = curr return prev if __name__ == '__main__': x = 1221 print('The total number of decodings are', count(x)) |
Output:
The total number of decodings are 5
Thanks for reading.
To share your code in the comments, please use our online compiler that supports C, C++, Java, Python, JavaScript, C#, PHP, and many more popular programming languages.
Like us? Refer us to your friends and support our growth. Happy coding :)