Given a digit sequence S, the task is to find the number of possible decodings of the given digit sequence where 1 represents ‘A’, 2 represents ‘B’ … and so on up to 26, where 26 represents ‘Z’.
Examples:
Input: S = “121”
Output: 3
The possible decodings are “ABA”, “AU”, “LA”Input: S = “1234”
Output: 3
The possible decodings are “ABCD”, “LCD”, “AWD”
Approach: In order to solve this problem in O(N) time complexity, Dynamic Programming is used. And in order to reduce the auxiliary space complexity to O(1), we use the space optimized version of recurrence relation discussed in the Fibonacci Number Post.
Similar to the Fibonacci Numbers, the key observations of any current ‘ith‘ index can be calculated using its previous two indices. So the Recurrence Relation to calculate the ith index can be denoted as
// Condition to check last
// digit can be included or not
if (digit[i-1] is not '0')
count[i] += count[i-1]
// Condition to check the last
// two digits contribution
if (digit[i-2] is 1 or
(digit[i-2] is 2 and
digit[i-1] is less than 7))
count[i] += count[i-2]
Below is the implementation of the above approach:
C++
// C++ implementation to count decodings#include <bits/stdc++.h>using namespace std;// A Dynamic Programming based function// to count decodings in digit sequenceint countDecodingDP(string digits, int n){ // For base condition "01123" // should return 0 if (digits[0] == '0') return 0; int count0 = 1, count1 = 1, count2; // Using last two calculated values, // calculate for ith index for (int i = 2; i <= n; i++) { count2 = ((int)(digits[i - 1] != '0') * count1) + (int)((digits[i - 2] == '1') or (digits[i - 2] == '2' and digits[i - 1] < '7')) * count0; count0 = count1; count1 = count2; } // Return the required answer return count1;}// Driver Codeint main(){ string digits = "1234"; int n = digits.size(); // Function call cout << countDecodingDP(digits, n); return 0;} |
Java
// Java implementation to count decodingsclass GFG{// A Dynamic programming based function// to count decodings in digit sequencestatic int countDecodingDP(String digits, int n){ // For base condition "01123" // should return 0 if (digits.charAt(0) == '0') { return 0; } int count0 = 1, count1 = 1, count2; // Using last two calculated values, // calculate for ith index for(int i = 2; i <= n; i++) { int dig1 = 0, dig2, dig3 = 0; // Change boolean to int if(digits.charAt(i - 1) != '0') { dig1 = 1; } if(digits.charAt(i - 2) == '1') { dig2 = 1; } else dig2 = 0; if(digits.charAt(i - 2) == '2' && digits.charAt(i - 1) < '7') { dig3 = 1; } count2 = dig1 * count1 + dig2 + dig3 * count0; count0 = count1; count1 = count2; } // Return the required answer return count1;}// Driver Codepublic static void main(String[] args){ String digits = "1234"; int n = digits.length(); // Function call System.out.print(countDecodingDP(digits, n));}}// This code is contributed by 29AjayKumar |
Python3
# Python3 implementation # to count decodings# A Dynamic programming based # function to count decodings # in digit sequencedef countDecodingDP(digits, n): # For base condition "01123" # should return 0 if (digits[0] == '0'): return 0; count0 = 1; count1 = 1; # Using last two calculated values, # calculate for ith index for i in range(2, n + 1): dig1 = 0; dig3 = 0; # Change boolean to int if (digits[i-1] != '0'): dig1 = 1; if (digits[i - 2] == '1'): dig2 = 1; else: dig2 = 0; if (digits[i - 2] == '2' and digits[i-1] < '7'): dig3 = 1; count2 = dig1 * count1 + dig2 + dig3 * count0; count0 = count1; count1 = count2; # Return the required answer return count1;# Driver Codeif __name__ == '__main__': digits = "1234"; n = len(digits); # Function call print(countDecodingDP(digits, n));# This code is contributed by gauravrajput1 |
C#
// C# implementation to count decodingsusing System;class GFG{// A Dynamic programming based function// to count decodings in digit sequencestatic int countDecodingDP(String digits, int n){ // For base condition "01123" // should return 0 if (digits[0] == '0') { return 0; } int count0 = 1, count1 = 1, count2; // Using last two calculated values, // calculate for ith index for(int i = 2; i <= n; i++) { int dig1 = 0, dig2, dig3 = 0; // Change bool to int if(digits[i - 1] != '0') { dig1 = 1; } if(digits[i - 2] == '1') { dig2 = 1; } else dig2 = 0; if(digits[i - 2] == '2' && digits[i - 1] < '7') { dig3 = 1; } count2 = dig1 * count1 + dig2 + dig3 * count0; count0 = count1; count1 = count2; } // Return the required answer return count1;}// Driver Codepublic static void Main(String[] args){ String digits = "1234"; int n = digits.Length; // Function call Console.Write(countDecodingDP(digits, n));}}// This code is contributed by Amit Katiyar |
Javascript
<script>// Javascript implementation to count decodings// A Dynamic Programming based function// to count decodings in digit sequencefunction countDecodingDP(digits, n){ // For base condition "01123" // should return 0 if (digits[0] == '0') return 0; var count0 = 1, count1 = 1, count2; // Using last two calculated values, // calculate for ith index for (var i = 2; i <= n; i++) { count2 = ((digits[i - 1] != '0') * count1) + ((digits[i - 2] == '1') || (digits[i - 2] == '2' && digits[i - 1] < '7')) * count0; count0 = count1; count1 = count2; } // Return the required answer return count1;}// Driver Codevar digits = "1234";var n = digits.length;// Function calldocument.write( countDecodingDP(digits, n));</script> |
Output:
3
Time Complexity: O(N)
Auxiliary Space Complexity: O(1)
Related Article: Count Possible Decodings of a given Digit Sequence
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
