ProDeveloperTutorial.com

Tutorials and Programming Solutions
Menu
  • Shell Scripting
  • System Design
  • Linux System Programming
  • 4g LTE
  • Coding questions
  • C
  • C++
  • DSA
  • GIT

Letter Combinations of a Phone Number, solution in C++

prodevelopertutorial July 29, 2018

Problem statement:

You are given a string of digits from 2 to 9 that represents mapping of phone number as shown below. Return all the possible letter combinations.

A mapping of the digit is similar to phone number as shown below.

Letter Combinations of a Phone Number

Below is the sample input and output:

Input: "23"

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

Note: 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 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 the 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 the inner loop for “characters_loop”. It will iterate for the times of the size of the 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

The solution for the iterative method in C++

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

vector<string> letterCombinations(string digits) 
{
    vector<string> res;
    string charmap[10] = {"0", "1", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
    res.push_back("");
    for (int i = 0; i < digits.size(); i++)
    {
        vector<string> tempres;
        string chars = charmap[digits[i] - '0'];
        cout<<"chars = "<<chars<<endl;
        cout<<"digits[i] = "<<digits[i]<<endl;
        cout<<"digits[i] - '0' = "<<digits[i] - '0'<<endl;


        for (int c = 0; c < chars.size();c++)
        {
            for (int j = 0; j < res.size();j++)
            {
                cout<<"res[j]= "<<res[j]<<endl;
                cout<<"chars[c]= "<<chars[c]<<endl;
                cout<<"res[j]+chars[c]= "<<res[j]+chars[c]<<endl;


                tempres.push_back(res[j]+chars[c]);
            }
            cout<<"==============="<<endl;
        }
        res = tempres;
    }
    return res;
}

int main()
{
    string digits = "23";
     vector<string> res = letterCombinations(digits);

    for (auto &i : res) 
    {
            for (auto &j : i)
                cout << j;
            cout << ' ';
    }
        cout << endl;
}
    

Output:

ad bd cd ae be ce af bf cf

Backtracking method:

For an introduction to backtrack please read the below article that I have written.

https://www.prodevelopertutorial.com/given-an-array-of-non-repeating-numbers-and-a-key-find-all-the-unique-combinations-in-that-array-where-the-sum-of-those-combination-is-equal-to-the-key/

Using the backtracking method, the solution is very simple.

The solution is based on the fact that; if the length of the letter combination is equal to the length of the digits, we shall write it in our final result set.

Example:

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

Input: 234
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

As you can see here, the length of the output combination is equal to the length of the digits.

Hence we shall call the “get_combination_backtrack” function recursively, and if the length of the combined string is equal to the length of the digits we shall push it to our final result set.

Out backtrack function “get_combination_backtrack” takes 5 parameters:

  1. Mapping of letters and digits
  2. Final result set
  3. Local variable for storing intermediate result
  4. Start index
  5. Digits from input

The 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 bd cd ae be ce af bf cf

List Of Tutorials available in this website:

C Programming 20+ ChaptersC++ Programming 80+ Chapters
100+ Solved Coding QuestionsData Structures and Algorithms 85+ Chapters
System design 20+ ChaptersShell Scripting 12 Chapters
4g LTE 60+ ChaptersMost Frequently asked Coding questions
5G NR 50+ ChaptersLinux System Programming 20+ chapters
Share
Email
Tweet
Linkedin
Reddit
Stumble
Pinterest
Prev Article
Next Article

About The Author

prodevelopertutorial

Daily we discuss about competitive programming questions, join us at:   Telegram Channel

ProDeveloperTutorial.com

Tutorials and Programming Solutions
Copyright © 2020 ProDeveloperTutorial.com
Get top courses from: Educative.io