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.
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.
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:
- Mapping of letters and digits
- Final result set
- Local variable for storing intermediate result
- Start index
- 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
