Combinations of words formed by replacing given numbers with corresponding alphabets

Given a set of positive numbers, find all possible combinations of words formed by replacing the continuous digits with corresponding character of English alphabet. i.e. subset {1} can be replaced by A, {2} can be replaced by B, {1, 0} can be replaced J, {2, 1} can be replaced U, etc..


 

For example,


Input:  digits[] = { 1, 2, 2 }
Output: ABB, AV, LB


{1, 2, 2} = ABB
{1, 22} = AV
{12, 2} = LB
 


Input:  digits[] = { 1, 2, 2, 1 }
Output: ABBA, ABU, AVA, LBA, LU


{1, 2, 2, 1} = ABBA
{1, 2, 21} = ABU
{1, 22, 1} = AVA
{12, 2, 1} = LBA
{12, 21} = LU

 

 

For every i’th element of the input, there are two possibilities – either this i’th will be combined with (i+1)’th element if the number formed by the them is less than equal to 26 or i’th element itself will form a new character. We recurse with remaining digits by considering both possibilities.

 

C++

Download   Run Complete Code

Java

Download   Run Code

Output:

ABB
AV
LB

 

 
We can also solve this problem by using Binary Tree and Recursion. The basic idea remains the same –

For every i’th element of the input, there are two possibilities – either this i’th will be combined with (i+1)’th element if the number formed by the them is less than equal to 26 or i’th element itself will form a new character. We recurse with remaining digits by considering both possibilities.

The only difference is instead of using string to store the output, we use binary tree nodes. Below code constructs a binary tree where each leaf node contains one unique combination of words formed.

 

C++

Download   Run Complete Code

Java

Download   Run Code

Output:

ABBA ABU AVA LBA LU

 
The time complexity of both solutions is exponential.

 
1 Star2 Stars3 Stars4 Stars5 Stars (1 votes, average: 5.00 out of 5)

Loading...

Thanks for reading.

Please use our online compiler to post code in comments. To contribute, get in touch with us.
Like us? Please spread the word and help us grow. Happy coding 🙂
 


Leave a Reply

avatar
  Subscribe  
newest oldest most voted
Notify of
arandomguy
Guest

Why alphabet string is declared static?