In letter combinations of a phone number problem, we have given a string containing numbers from 2 to 9. The problem is to find all the possible combinations that could be represented by that number if every number has some letters assigned to it. The assignment of the number is given below it is just like the telephone buttons.
Note that no letter is assigned to 1 here
Table of Contents
Example
"23"
["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"]
The letters assigned to “2” are “ABC” and to “3” are “DEF” therefore the combination of letters will be “ad”, “ae”, “af”, “bd”, “be”, “bf”, “cd”, “ce” and “cf”
Algorithm
- Declare a Queue and an ArrayList and string array.
- String array should store the values as given string keyWords[10]= { “”, “”, “abc”, “def”, “ghi”, “jkl”, “mno”, “pqrs”, “tuv”, “wxyz” };
- At first, push an empty string into a queue
- While queue has some values in it iterates over the loop.
- Store the value of the queue’s front to a temporary string
- If the length of temporary string found to be equal to n (which is input value length) then
- Add the value of the temporary string to list.
- Else, open a loop in which string value is initialized as a copy = keys[number[temp.length()]];
- Add the temp string to every keyword’s substring(0, 1) and push it in the queue.
- Iterates over it until the queue has values in it.
- Return list.
Explanation
Suppose we are given input as 23. Then we change it to an integer. And convert it into an array of digits in the same manner as we have got it. And we will pass the input Value and length of that input value into the function which we have made named as a combination.
In that function we also initialized our keywords string keyWords[10]={ “”, “”, “abc”,”def”, “ghi”, “jkl”,”mno”, “pqrs”, “tuv”, “wxyz” }
We pass these values in another function called getCombination in which we get the output.
So we take 23 as an example it is stored in array={2, 3} at 0, 1 index respectively.
So now in a function, we declared a queue and a list which is going to store our output.
We push an empty string into que;
que= “”;
Entering in a while loop: we get the queue’s front into temp and remove it from que,
Temp= “”
Now if a part doesn’t execute because the values are different from temp and n. So it executes else part which will do the
Copy = temp.length=0 => number[0] = 2 => keys[2]= “abc”
Which means copy= “abc”;
Now it gonna iterate in for loop
And add the que in a, b and c.
Now again it checks while(!que.isEmpty()) and it is true so it keeps going and it takes queue’s front in temp that is “a” and remove a.
Copy = temp.length=1 => number[1] = 3 => keys[3]= “def”
So now it gonna append a with d, e and f and push it in queue respectively.
Now again it checks while(!que.isEmpty()) and it is true so it keeps going and it takes queue’s front in temp that is “b” now and remove b.
Copy = temp.length=1 => number[1] = 3 => keys[3]= “def”
So now it gonna append b with d, e and f and push it in queue respectively.
Now again it checks while(!que.isEmpty()) and it is true so it keeps going and it takes queue’s front in temp that is “c” and remove c.
Copy = temp.length=1 => number[1] = 3 => keys[3]= “def”
So now it gonna append c with d, e and f and push it in queue respectively.
Now if it takes queue’s front in temp that and found that temp.length is equal to n. And add the temp and sequentially it is going to add every combination we get.
And we get the output: ( ad, ae, af, bd, be, bf, cd , ce , cf )
Implementation
C++ Program to find Letter Combinations of a Phone Number
#include<iostream>
#include<queue>
#include<sstream>
using namespace std;
vector<string> getCombination( int inputValue[], int n, string keyWords[])
{
vector<string> list;
queue<string> que;
que.push("");
while (!que.empty())
{
string temp = que.front();
que.pop();
if (temp.length() == n)
list.push_back(temp);
else
for (auto getword : keyWords[inputValue[temp.length()]])
que.push(temp + getword);
}
return list;
}
void combination( int inputValue[], int n)
{
string keyWords[10]
= { "", "", "abc", "def", "ghi", "jkl",
"mno", "pqrs", "tuv", "wxyz"
};
vector<string> list= getCombination(inputValue, n, keyWords);
for (auto word : list)
cout << word << " ";
return;
}
int main()
{
string s="23";
stringstream comb(s);
int le=s.length();
int inputValue[le];
int i=0,x=0;
comb>>x;
while(x>0)
{
inputValue[le-i-1]=x%10;
x/=10;
i++;
}
int lengths = sizeof(inputValue) / sizeof(inputValue[0]);
combination(inputValue, lengths);
return 0;
}
ad ae af bd be bf cd ce cf
Java Program to find Letter Combinations of a Phone Number
import java.util.*;
class combinationNumber {
static ArrayList<String> getCombination(int[] number, int n, String[] keys) {
ArrayList<String> getList = new ArrayList<>();
Queue<String> que = new LinkedList<>();
que.add("");
while (!que.isEmpty()) {
String temp = que.remove();
if (temp.length() == n)
getList.add(temp);
else {
String copy = keys[number[temp.length()]];
for (int i = 0; i<copy.length(); i++) {
que.add(temp + copy.charAt(i));
}
}
}
return getList;
}
static void combination(int[] inputValue, int n) {
String[] keyWords = {
"", "", "abc", "def", "ghi", "jkl",
"mno", "pqrs", "tuv", "wxyz"
};
ArrayList<String> output = getCombination(inputValue, n, keyWords);
for (int i = 0; i<output.size(); i++) {
System.out.print(output.get(i) + " ");
}
}
public static void main(String args[]) {
String s = "23";
int numb = Integer.valueOf(s);
int i = 0;
int[] inputValue = new int[s.length()];
while (numb > 0) {
inputValue[s.length() - i - 1] = numb % 10;
numb /= 10;
i++;
}
int lengths = inputValue.length;
combination(inputValue, lengths);
}
}ad ae af bd be bf cd ce cf
Complexity Analysis
Time Complexity
O(3N × 4M) where N is the number of digits which have 3 letters( ex: 2,3,4) assigned to it and M is the number of digits which has 4 letters(ex: 7,9) assigned to it.
Space Complexity
O(3N × 4M) where N is the number of digits which have 3 letters( ex: 2,3,4) assigned to it and M is the number of digits which has 4 letters(ex: 7,9) assigned to it.