Generate All Strings

Moderate
0/80
Average time to solve is 25m
profile
Contributed by
7 upvotes
Asked in company
Walmart

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.

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].
Detailed explanation ( Input/output format, Notes, Images )
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
Sample Input 1 :
2
1123
125
Sample Output 1 :
aabc aaw alc kbc kw
abe ay le
Explanation Of Sample Input 1 :
For the first case:
aabc => a=1, a=1, b=2, c=3
aaw => a=1, a=1, w=23
alc => a=1, l=12, c=3
kbc => k=11, b=2, c=3
kw => k=11, w=23
Sorting the strings in lexicographical order, so the final output is [aabc, aaw, alc, kbc, kw].

For the second case:
abe => a=1, b=2, e=5
le => l=12, e=5
Sorting the strings in lexicographical order, the final output is [abe le].
Sample Input 2 :
2
721023
871121
Sample Output 2 :
gbjbc gbjw 
hgaaba hgaau hgala hgkba hgku
Hint

Can you think of any way solution using backtracking?

Approaches (1)
Backtracking

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):

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


 

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

Function isValid(string& s):

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

 

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

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

  1. If the 'IDX' is at the end of the string 'S' then insert 'curStr' into the set 'ANS' and return.
  2. If the character at ‘IDX’ is 0 then return.
  3. Declare an empty string 'NUM' to store the current digit value.
  4. Add the current digit value to 'NUM'.
  5. Convert 'NUM' from digit to character, call convertDigitToAlpha  function and store it into a character 'curCh'.
  6. Append the character 'curCh' into 'curStr'.
  7. Recursively call the getAllStringsUtil function to get the final string with 'curCh' as its current character.
  8. Pop-out the 'curCh' character from 'curStr'.
  9. 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):

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

O( M * log( M ) ), Where ‘M’ = 2^N and ‘N’ denotes the length of the string. 

 

For each character, we have two choices either treat it as a single digit or as a two-digit. We are recursively finding all the possible strings and in the worst case there will be a 2^’N’ number of strings For each possible string we are inserting it into the set.

Hence the time complexity is O( M * log( M ) ).

Space Complexity

O( M ), Where ‘M’ = 2^N and ‘N’ denotes the length of the string. 

 

We are using a set ‘ANS’ to store all the possible strings.

Hence space complexity is O( M ).

Code Solution
(100% EXP penalty)
Generate All Strings
Full screen
Console