Last Updated: 9 Jul, 2022

Generate All Strings

Moderate

Asked in company

Solve now

Problem statement

You are given a string ‘S’ of length ‘N’ which consists of digits from 0 to 9 only. If the mapping of characters from a to z is like a = 1, b = 2, c = 3…. Z = 26. You need to convert the given string of digits into the string of characters using the mapping.

Print all the possible strings that can be generated from the given string ‘S’. Print the strings in non-decreasing sorted lexicographical order.

Example:

‘S’ = “112”. 

Output: [aab, al, kb]

The possible ways to convert the given strings is: 
aab => a = 1, a = 1, b = 2,
al => a = 1, l = 12
kb => k = 11, b = 2
Hence, the final array is: [aab, al, kb].

Input Format :

The first line will contain the integer 'T', denoting the number of test cases.

The first line of each test case contains a string ‘S’.

Output format :

For each test case, you don’t need to print anything just return an array of all possible strings sorted in non-decreasing lexicographical order.

Note :

You don't need to print anything. It has already been taken care of. Just implement the given function.

Constraints :

1 <= T <= 10
1 <= S.length <= 20
Sum of length of strings over all test cases <= 20

Time Limit: 1 sec

Solve now

Approaches

01 Approach

In this approach, For each character, we may have two possibilities, either we treat it as a single digit to get the character from 1 to 9 or we append the next digit with it. We recursively try all the possible combinations. We can use a set to store all the strings in sorted order.

The steps are as follows:-

// Function to convert a one digit string or two digit string into a character.
Function convertDigitToAlpha(string digit):

Initialize a variable 'digVal' with 0.
Add the value of the first digit to 'digVal'.
If the 'digit' string size is greater than one, multiply the current ‘digVal’ by 10 and add the second digit value to the 'digVal'.
Return the character obtained from 'digVal'.

// Function to check if the digit string is less than 27 or not.

Function isValid(string& s):

Convert the string into an integer, if it is greater than 26 or the first digit is '0' then return false.
Else return true.

// // Recursive function to get all possible strings.

Function getAllStringsUtil(string& s, int idx, string& curStr, set<string>& ans):

If the 'IDX' is at the end of the string 'S' then insert 'curStr' into the set 'ANS' and return.
If the character at ‘IDX’ is 0 then return.
Declare an empty string 'NUM' to store the current digit value.
Add the current digit value to 'NUM'.
Convert 'NUM' from digit to character, call convertDigitToAlpha function and store it into a character 'curCh'.
Append the character 'curCh' into 'curStr'.
Recursively call the getAllStringsUtil function to get the final string with 'curCh' as its current character.
Pop-out the 'curCh' character from 'curStr'.
If the 'IDX' is not equal to 'N'-1.
Add the digit at 'IDX'+1 to the 'NUM'.
Call the 'isValid' function to check if ‘NUM’ is valid.
Call 'convertDigitToAlpha' to conver 'NUM' into a character and store it in 'curCh'.
Append the character 'curCh' into 'curStr'.
Recursively call the getAllStringsUtil function to get the final string with 'curCh' as its current character.
Pop-out the 'curCh' character from 'curStr'.

Function getAllStringsUtil(string& s):

Declare a set 'ANS' to store all the possible strings.
Declare an empty string 'curStr'.
Call getAllStringsUtil with 'S', 'curStr', 'ANS' and index as 0 as the arguments.
Declare an array 'finalList' to store all the strings in set 'ANS'.
Iterate over all the strings in set 'ANS' and insert it into 'finalList'.
Return the 'finalList' array.

Solve now

Generate All Strings

Problem statement

You are given a string ‘S’ of length ‘N’ which consists of digits from 0 to 9 only. If the mapping of characters from a to z is like a = 1, b = 2, c = 3…. Z = 26. You need to convert the given string of digits into the string of characters using the mapping.

Print all the possible strings that can be generated from the given string ‘S’. Print the strings in non-decreasing sorted lexicographical order.

Example:

Input Format :

Output format :

Note :

Constraints :

Approaches

01 Approach

The steps are as follows:-

// Function to convert a one digit string or two digit string into a character.Function convertDigitToAlpha(string digit):

Function isValid(string& s):

Function getAllStringsUtil(string& s, int idx, string& curStr, set<string>& ans):

Function getAllStringsUtil(string& s):

// Function to convert a one digit string or two digit string into a character.
Function convertDigitToAlpha(string digit):