Letter Combinations of a Phone Number

Problem statement:

Given a string containing digits from 2-9 inclusive, return all possible letter combinations that the number could represent.
A mapping of digit to letters (just like on the telephone buttons) is given below. Note that 1 does not map to any letters.

Below is the sample input and output:

Input: "23"
Output: ["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"].

The order of the output can be anything.

We can solve this problem by using any techniques like iterative, recursive, backtrack, DFS. Here we shall discuss about 2 solutions, Iterative method and Backtrack method.

Solution 1: Iterative method:

In this method, we shall be taking 3 for loops. Let’s call them as:
digits_loop: It will iterate for the length of the digit times. For example, if the input is “23”, it will iterate 2 times. If input is “234” it will iterate 3 times.
characters_loop: This is the inner loop for the “digits_loop”. For single digit, it will take the letters for that digit. It will iterate for the times of letters count for that digit. For example, if the digit is 2, then letters are “abc”, it will iterate for 3 times. If the digit is 9, then the letters are “wxyz”, it will iterate for 4 times.
combination_loop: It is inner loop for “characters_loop”. It will iterate for the times of the size of result set.

Note: As the input digits are in string format, and cannot be used in for loops. They need to be converted into integers. We do that by using “ digits[i] – ‘0’ ” formula.

Let us take an example and understand it.
Input digit = 23

result_set initially will be of size 1
According to the input, digits_loop will iterate for 2 times

Pass 1 of digits_loop :
	string chars = digit_letter_mapping[digits[i] - '0'];
		chars ="abc"
	characters_loop run for 3 times
		pass 1 of characters_loop
			combination_loop run for 1 time
			temp = a
		
		pass 2 of characters_loop
			combination_loop run for 1 time
			temp = b
		pass 3 of characters_loop
			combination_loop run for 1 time
			temp = b

Pass 2 of digits_loop :

	string chars = digit_letter_mapping[digits[i] - '0'];
		chars ="def"
	characters_loop run for 3 times
		pass 1 of characters_loop
			combination_loop run for 3 time
			pass 1 of characters_loop
				temp = ad
			pass 2 of characters_loop
				temp = bd
			pass 3 of characters_loop
				temp = cd

		pass 2 of characters_loop
			combination_loop run for 3 time
			pass 1 of characters_loop
				temp = ae
			pass 2 of characters_loop
				temp = be
			pass 3 of characters_loop
				temp = ce

		pass 3 of characters_loop
			combination_loop run for 3 time
			pass 1 of characters_loop
				temp = af
			pass 2 of characters_loop
				temp = bf
			pass 3 of characters_loop
				temp = cf

Solution for iterative method in C++

#include<iostream>
#include<vector>
using namespace std;

vector<string> getLetterCombination(string digits) 
{
    vector<string> final_result_set ;
    string digits_letter_combination_map [10] = {"0", "1", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};

    final_result_set.push_back(""); // initially initialize it to 1


    for (int digits_loop = 0; digits_loop < digits.size(); digits_loop++)
    {
        vector<string> temp_result_set;
        string letters = digits_letter_combination_map [ digits[digits_loop] - '0'];


        for (int characters_loop = 0; characters_loop < letters.size(); characters_loop++)
        {
            for (int combination_loop = 0; combination_loop < final_result_set.size(); combination_loop++)
            {
                temp_result_set.push_back( final_result_set [ combination_loop ]+ letters[ characters_loop ]);
            }
        }
        final_result_set = temp_result_set;
    }
    return final_result_set;
}

int main()
{
    string digits = "23";
    vector<string> final_result = getLetterCombination(digits);

    for (int i = 0; i < final_result.size(); i++)
                cout << final_result[i] << " ";
    cout<<endl;

}

Output:

ad bd cd ae be ce af bf cf

Backtracking method:

Solution for backtrack in C++

#include<iostream>
#include<vector>
using namespace std;



void get_combination_backtrack( string digits_letter_combination_map[], vector<string>& final_result_set, string& local_storage, int index, string& digits) 
{
        if(index==digits.size())
            final_result_set.push_back(local_storage);
        else
            for(int i=0;i<digits_letter_combination_map[digits[index]-'0'].size();i++) 
            {
                local_storage.push_back(digits_letter_combination_map[digits[index]-'0'][i]);
                get_combination_backtrack(digits_letter_combination_map, final_result_set, local_storage, index+1, digits);
                local_storage.pop_back();
            }
}


vector<string> getLetterCombination(string digits) 
{
	vector<string> final_result_set;
    string digits_letter_combination_map [10] = {"0", "1", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
    string local_storage;

    get_combination_backtrack(digits_letter_combination_map, final_result_set,local_storage, 0, digits);

    return final_result_set;
}



int main()
{
    string digits = "23";
    vector<string> final_result = getLetterCombination(digits);

    for (int i = 0; i < final_result.size(); i++)
                cout << final_result[i] << " ";
    cout<<endl;

}

Output:

ad ae af bd be bf cd ce cf