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++ implementation –
 

Download   Run Complete 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++ implementation –
 

Download   Run Complete Code

Output:

ABBA ABU AVA LBA LU

 
The time complexity of both solutions is exponential.
 

Thanks for reading.




Please use ideone or C++ Shell or any other online compiler link to post code in comments.
Like us? Please spread the word and help us grow. Happy coding 🙂
 





Leave a Reply

Notify of
avatar
wpDiscuz