New update is available. Click here to update.

Solve problems & track your progress

Checkout your overall progress in every topic here

Become

Sensei

in DSA topics

Open the topic and solve more problems associated with it to improve your skills

Check out the skill meter for every topic

See how many problems you are left with to solve for cracking any stage. Score more than zero to get your progress counted.

Problem

Submissions

Generate All Strings

Contributed by

Amit Shaw

Medium

0/80

Avg time to solve 25 mins

Success Rate 52 %

0 upvotes

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].

Detailed explanation ( Input/output format, Notes, Constraints, 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

Auto

Console