Print all possible words from phone digits

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;
}

Try It

 

Translate »