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

## Java

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.

## Java

Output:

ABBA ABU AVA LBA LU

The time complexity of both solutions is exponential.     (2 votes, average: 5.00 out of 5) Loading...

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 🙂 Subscribe
Notify of Guest
arandomguy

Why alphabet string is declared static? Guest
Raj Kumar Soni

This question can be solve in O(n) complexity in java