Find all possible combinations of words formed from mobile keypad

Given a sequence of numbers between [2-9], print all possible combinations of words formed from mobile keypad have some digits associated with each key.


 

keypad
 


Input: [2, 3, 4]

Output:

ADG BDG CDG AEG BEG CEG AFG BFG CFG ADH BDH CDH AEH BEH
CEH AFH BFH CFH ADI BDI CDI AEI BEI CEI AFI BFI CFI

 
We can use Recursion to solve this problem. The idea is to consider every input digit one by one, replace the digit with each character in the mobile keypad and recurse for the next digit. When all the digit are processed, we print the result.

 
Below is C++ and Java implementation of the idea –

C++

Download   Run Code

Java

Download   Run Code

Output:

ADG BDG CDG AEG BEG CEG AFG BFG CFG ADH BDH CDH AEH BEH CEH AFH BFH CFH ADI BDI CDI AEI BEI CEI AFI BFI CFI

 

Iterative implementation –

We can also solve this problem iteratively using a vector. The idea remains the same but instead of recursing, we push the partial-word into the vector. For each character associated with current digit in the keypad, we append the character to each word in the output list and push the result to the vector. So at the end of each iteration, vector contains all possible combinations of words till current digit. We repeat this process until all digits are processed.

 
Below is C++ and Java implementation of the idea –

C++

Download   Run Code

Java

Download   Run Code

Output:

[ADG, BDG, CDG, AEG, BEG, CEG, AFG, BFG, CFG, ADH, BDH, CDH, AEH, BEH, CEH, AFH, BFH, CFH, ADI, BDI, CDI, AEI, BEI, CEI, AFI, BFI, CFI]

 

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

avatar
  Subscribe  
Notify of