Print all Possible Decodings of a given Digit Sequence
Given the numeric string str, where 1 represents βaβ, 2 represents βbβ, β¦, 26 represents βzβ, the task is to print all possible alphabetical strings that can be obtained from str.
Examples:
Input: str = β1123β
Output:
aabc
kbc
alc
aaw
kw
Explanation:
The given string can be splitted as:
1) β1123β = β1β + β1β + β2β + β3β = aabc
2) β1123β = β11β + β2β + β3β = kbc
3) β1123β = β1β + β12β + β3β = alc
4) β1123β = β1β + β1β + β23β = aaw
5) β1123β = β11β + β23β = aabcInput: str = β56β
Output:
ef
Explanation:
The given string can be splitted as:
1) β56β = β5β + β6β = ef
Approach: It can be observed that every single character represents an alphabet apart from 0. This problem is recursive and can be broken into sub-problems. The terminating condition will be when the passed string is empty. Below are the steps to solve the problem:
- Create a helper function getChar() that returns the corresponding alphabet of the given numeric character.
- Create a recursive function that takes the input as a string and returns an array of the desired answer of every character extracted.
- The base case is when the input string is empty. Return an array of length one containing an empty string for this case.
- Extract every single character by using the helper function and append it to the empty string first and store it in an array, say output1.
- At the same time check if the length of the characters is greater than or equal to two and also check if the two characters extracted lies in the range of alphabets. Now, store the corresponding character in an array, say output2.
- Then create a final output array whose length will be the sum of the length of output1 and output2 and store their answers and return it.
- Repeat the above steps for every single or pair of adjacent characters extracted. Now, return the final array obtained.
- Traverse the array and for each string, generate corresponding strings of lowercase alphabets and print them.
Below is the implementation of the above approach:
C++
// C++ program for the above approach #include<bits/stdc++.h> using namespace std; // Function to check if all the // characters are lowercase or not bool nonLower(string s) { // Traverse the string for ( int i = 0; i < s.size(); i++) { // If any character is not // found to be in lowerCase if (! islower (s[i])) { return true ; } } return false ; } // Function to print the decodings void printCodes(vector<string> output) { for ( int i = 0; i < output.size(); i++) { // If all characters are not // in lowercase if (nonLower(output[i])) continue ; cout << (output[i]) << endl; } } // Function to return the character // corresponding to given integer char getChar( int n) { return ( char )(n + 96); } // Function to return the decodings vector<string> getCode(string str) { // Base case if (str.size() == 0) { vector<string> ans; ans.push_back( "" ); return ans; } // Recursive call vector<string> output1 = getCode(str.substr(1)); // Stores the characters of // two digit numbers vector<string> output2(0); // Extract first digit and // first two digits int firstDigit= (str[0] - '0' ); int firstTwoDigit = 0; if (str.size() >= 2) { firstTwoDigit = (str[0] - '0' ) * 10 + (str[1] - '0' ); // Check if it lies in the // range of alphabets if (firstTwoDigit >= 10 && firstTwoDigit <= 26) { // Next recursive call output2 = getCode(str.substr(2)); } } // Combine both the output in a // single final output array vector<string> output(output1.size() + output2.size()); // Index of final output array int k = 0; // Store the elements of output1 // in final output array for ( int i = 0; i < output1.size(); i++) { char ch = getChar(firstDigit); output[i] = ch + output1[i]; k++; } // Store the elements of output2 // in final output array for ( int i = 0; i < output2.size(); i++) { char ch = getChar(firstTwoDigit); output[k] = ch + output2[i]; k++; } // Result the result return output; } // Driver Code int main() { string input = "101" ; // Function call vector<string> output = getCode(input); // Print function call printCodes(output); } // This code is contributed by grand_master |
Java
// Java program for the above approach import java.io.*; class GFG { // Function to check if all the // characters are lowercase or not public static boolean nonLower(String s) { // Traverse the string for ( int i = 0 ; i < s.length(); i++) { // If any character is not // found to be in lowerCase if (!Character .isLowerCase(s.charAt(i))) { return true ; } } return false ; } // Function to print the decodings public static void printCodes(String output[]) { for ( int i = 0 ; i < output.length; i++) { // If all characters are not // in lowercase if (nonLower(output[i])) continue ; System.out.println(output[i]); } } // Function to return the character // corresponding to given integer public static char getChar( int n) { return ( char )(n + 96 ); } // Function to return the decodings public static String[] getCode( String str) { // Base case if (str.length() == 0 ) { String ans[] = { "" }; return ans; } // Recursive call String output1[] = getCode(str.substring( 1 )); // Stores the characters of // two digit numbers String output2[] = new String[ 0 ]; // Extract first digit and // first two digits int firstDigit = (str.charAt( 0 ) - '0' ); int firstTwoDigit = 0 ; if (str.length() >= 2 ) { firstTwoDigit = (str.charAt( 0 ) - '0' ) * 10 + (str.charAt( 1 ) - '0' ); // Check if it lies in the // range of alphabets if (firstTwoDigit >= 10 && firstTwoDigit <= 26 ) { // Next recursive call output2 = getCode(str.substring( 2 )); } } // Combine both the output in a // single final output array String output[] = new String[output1.length + output2.length]; // Index of final output array int k = 0 ; // Store the elements of output1 // in final output array for ( int i = 0 ; i < output1.length; i++) { char ch = getChar(firstDigit); output[i] = ch + output1[i]; k++; } // Store the elements of output2 // in final output array for ( int i = 0 ; i < output2.length; i++) { char ch = getChar(firstTwoDigit); output[k] = ch + output2[i]; k++; } // Result the result return output; } // Driver Code public static void main(String[] args) { String input = "101" ; // Function call String output[] = getCode(input); // Print function call printCodes(output); } } |
Python3
# Python3 program for # the above approach # Function to check if all the # characters are lowercase or not def nonLower(s): # Traverse the string for i in range ( len (s)): # If any character is not # found to be in lowerCase if not s[i].islower(): return True return False # Function to print the decodings def printCodes(output): for i in range ( len (output)): # If all characters are not # in lowercase if (nonLower(output[i])): continue print (output[i]) # Function to return the character # corresponding to given integer def getChar(n): return chr (n + 96 ) # Function to return the decodings def getCode( str ): # Base case if ( len ( str ) = = 0 ): ans = [""] return ans # Recursive call output1 = getCode( str [ 1 :]) # Stores the characters of # two digit numbers output2 = [] # Extract first digit and # first two digits firstDigit = ( ord ( str [ 0 ]) - ord ( '0' )) firstTwoDigit = 0 if ( len ( str ) > = 2 ): firstTwoDigit = (( ord ( str [ 0 ]) - ord ( '0' )) * 10 + ( ord ( str [ 1 ]) - ord ( '0' ))) # Check if it lies in the # range of alphabets if (firstTwoDigit > = 10 and firstTwoDigit < = 26 ): # Next recursive call output2 = getCode( str [ 2 :]) # Combine both the output in a # single readonly output array output = ['' for i in range ( len (output1) + len (output2))] # Index of readonly output array k = 0 # Store the elements of output1 # in readonly output array for i in range ( len (output1)): ch = getChar(firstDigit) output[i] = ch + output1[i] k + = 1 # Store the elements of output2 # in readonly output array for i in range ( len (output2)): ch = getChar(firstTwoDigit) output[k] = ch + output2[i] k + = 1 # Result the result return output # Driver Code if __name__ = = '__main__' : input = "101" # Function call output = getCode( input ) # Print function call printCodes(output) # This code is contributed by rutvik_56 |
C#
// C# program for // the above approach using System; class GFG{ // Function to check if all the // characters are lowercase or not public static bool nonLower(String s) { // Traverse the string for ( int i = 0; i < s.Length; i++) { // If any character is not // found to be in lowerCase if (! char .IsLower(s[i])) { return true ; } } return false ; } // Function to print the decodings public static void printCodes(String []output) { for ( int i = 0; i < output.Length; i++) { // If all characters are not // in lowercase if (nonLower(output[i])) continue ; Console.WriteLine(output[i]); } } // Function to return the character // corresponding to given integer public static char getChar( int n) { return ( char )(n + 96); } // Function to return the decodings public static String[] getCode(String str) { // Base case if (str.Length == 0) { String []ans = { "" }; return ans; } // Recursive call String []output1 = getCode(str.Substring(1)); // Stores the characters of // two digit numbers String []output2 = new String[0]; // Extract first digit and // first two digits int firstDigit = (str[0] - '0' ); int firstTwoDigit = 0; if (str.Length >= 2) { firstTwoDigit = (str[0] - '0' ) * 10 + (str[1] - '0' ); // Check if it lies in the // range of alphabets if (firstTwoDigit >= 10 && firstTwoDigit <= 26) { // Next recursive call output2 = getCode(str.Substring(2)); } } // Combine both the output in a // single readonly output array String []output = new String[output1.Length + output2.Length]; // Index of readonly output array int k = 0; // Store the elements of output1 // in readonly output array for ( int i = 0; i < output1.Length; i++) { char ch = getChar(firstDigit); output[i] = ch + output1[i]; k++; } // Store the elements of output2 // in readonly output array for ( int i = 0; i < output2.Length; i++) { char ch = getChar(firstTwoDigit); output[k] = ch + output2[i]; k++; } // Result the result return output; } // Driver Code public static void Main(String[] args) { String input = "101" ; // Function call String []output = getCode(input); // Print function call printCodes(output); } } // This code is contributed by Rajput-Ji |
Javascript
<script> // Javascript program for the above approach // Function to check if all the // characters are lowercase or not function nonLower(s) { // Traverse the string for (let i = 0; i < s.length; i++) { // If any character is not // found to be in lowerCase if (!(s[i].charCodeAt() >= 97 && s[i].charCodeAt() <= 122)) { return true ; } } return false ; } // Function to print the decodings function printCodes(output) { for (let i = 0; i < output.length; i++) { // If all characters are not // in lowercase if (nonLower(output[i])) continue ; document.write(output[i] + "</br>" ); } } // Function to return the character // corresponding to given integer function getChar(n) { return String.fromCharCode(n + 96); } // Function to return the decodings function getCode(str) { // Base case if (str.length == 0) { let ans = [ "" ]; return ans; } // Recursive call let output1 = getCode(str.substring(1)); // Stores the characters of // two digit numbers let output2 = new Array(0); // Extract first digit and // first two digits let firstDigit = (str[0] - '0' ); let firstTwoDigit = 0; if (str.length >= 2) { firstTwoDigit = (str[0].charCodeAt() - '0' .charCodeAt()) * 10 + (str[1].charCodeAt() - '0' .charCodeAt()); // Check if it lies in the // range of alphabets if (firstTwoDigit >= 10 && firstTwoDigit <= 26) { // Next recursive call output2 = getCode(str.substring(2)); } } // Combine both the output in a // single readonly output array let output = new Array(output1.length + output2.length); // Index of readonly output array let k = 0; // Store the elements of output1 // in readonly output array for (let i = 0; i < output1.length; i++) { let ch = getChar(firstDigit); output[i] = ch + output1[i]; k++; } // Store the elements of output2 // in readonly output array for (let i = 0; i < output2.length; i++) { let ch = getChar(firstTwoDigit); output[k] = ch + output2[i]; k++; } // Result the result return output; } let input = "101" ; // Function call let output = getCode(input); // Print function call printCodes(output); // This code is contributed by mukesh07. </script> |
ja
Time Complexity: O(2N)
Space Complexity:O(N)