Table of Contents
Given a string of numbers, each number represents a number on the QWERTY keyboards, texts and numbers were placed on the same key.
0, 1 – NULL
2 – ABC, 3 – DEF, 4 – GHI, 5 – JKL, 6 – MNO, 7 – PQRS, 8 – TUV, 9 – WXYZ.
We need to print all possible words with given number. If 0 or 1 comes we need to break as there will no iteration for these digits.
Example
Input string : 234
Output : ADG, ADH, ADI, AEG, AEH, AEI, AFG, AFH, AFI, BDG, BDI, BEG, BEH, BEI, BFG, BFH, BFI, CDG, CEG, CEH, CEI, CFG, CFH, CFI
Algorithm
Here, we use recursion.
1. Create a database table to store all characters correspond to digit i in the keyboard.
2. We store all possible words that can be obtained by input string[] of size n.
3. We store words in output[].
4. Try all possible characters for current digit and recursion for remaining digits.
5. We print the final output array.
C++ Program
#include <bits/stdc++.h>
using namespace std;
const char DataArray[10][5] = {"", "", "ABC", "DEF", "GHI", "JKL","MNO", "PQRS", "TUV", "WXYZ"};
//recursion to print all possible
void Recursion(int string[], int current_length, char output[], int string_length)
{
int i;
if (current_length == string_length)
{
cout<<output<<",";
return;
}
//loop for all charcters according to given digits
for (i=0; i<strlen(DataArray[string[current_length]]); i++)
{
output[current_length] = DataArray[string[current_length]][i];
Recursion(string, current_length+1, output, string_length);
//If 0 or 1 comes return from there
if(string[current_length] == 0 || string[current_length] == 1)
{
return;
}
}
}
//call recurstion in this function
void PrintStrings(int string[], int string_length)
{
char output[string_length+1];
output[string_length] ='\0';
Recursion(string, 0, output, string_length);
}
//Driver program
int main(void)
{
int string[] = {2, 3, 4};
int string_length = sizeof(string)/sizeof(string[0]);
PrintStrings(string, string_length);
return 0;
}