Allow us to grasp the answer using the example below.
arr[{2, 3, 4}
First we create all sequences including one digit {2}, obtaining “a,” “b,” and “c.”
We then create all sequences with two digits {2, 3}, obtaining “ad,” “ae,” “af,” “bd,” “be,” “bf,” “cd,” “ce,” “cf.” We can just take all past sequences with one digit and one by one add all characters that fit three (“d”, “e“, “f”). We thus have 3 x 3 = 9 sequences.
We follow the same procedure for the last digit 4 and get 9 x 3 = 27 needed sequences.
The next sequence from the last one now begs the issue of how we got it. We mostly have to handle the FIFO order’s past sequence. For this reason, a queue would be absolutely ideal. We first construct result with i+1 digits by removing every item from queue and adding all characters corresponding to (i + 1)-th digit. We then queue result with i digits.
The above method is applied here below:
C++
#include <bits/stdc++.h>
using namespace std;
// Function to return a vector that contains all the
// generated letter combinations
vector<string> letterCombinations(vector<int> &a)
{
// mp[i] stores all characters that correspond to
// ith digit in phone
string mp[10] = { "0", "1", "abc", "def", "ghi",
"jkl", "mno", "pqrs", "tuv", "wxyz" };
// To store the generated letter combinations
vector<string> res;
// Queue to store intermediate combinations
queue<string> q;
q.push("");
// Process combinations using BFS-like approach
while (!q.empty()) {
string s = q.front();
q.pop();
// If complete word is generated,
// add to the result list
if (s.length() == a.size()) {
res.push_back(s);
} else {
// Try all possible letters for the
// current digit in the vector a
for (char c : mp[a[s.length()]]) {
q.push(s + c);
}
}
}
// Return the generated combinations
return res;
}
// Driver code
int main()
{
vector<int> a = {2, 3};
vector<string> res = letterCombinations(a);
for (const string &word : res)
cout << word << " ";
return 0;
}C
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>
// Function to return a dynamically allocated array of strings
char** letterCombinations(int* a, int size, int* returnSize) {
// mp[i] stores all characters that correspond to ith digit in phone
char* mp[] = { "0", "1", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz" };
// To store the generated letter combinations
char** res = malloc(1000 * sizeof(char*)); // Adjust size as needed
*returnSize = 0;
// Queue to store intermediate combinations
char* queue[1000];
int front = 0, rear = 0;
queue[rear++] = strdup(""); // Start with an empty string in the queue
// Process combinations using BFS-like approach
while (front < rear) {
char* s = queue[front++];
// If complete word is generated, add to the result list
if (strlen(s) == size) {
res[*returnSize] = s;
(*returnSize)++;
} else {
// Try all possible letters for the current digit in the vector a
int index = strlen(s);
const char* chars = mp[a[index]];
for (int i = 0; chars[i] != '\0'; i++) {
char* newStr = malloc(strlen(s) + 2);
strcpy(newStr, s);
newStr[strlen(s)] = chars[i];
newStr[strlen(s) + 1] = '\0';
queue[rear++] = newStr;
}
free(s);
}
}
return res;
}
// Driver code
int main() {
int a[] = {2, 3};
int size = sizeof(a) / sizeof(a[0]);
int returnSize;
char** res = letterCombinations(a, size, &returnSize);
for (int i = 0; i < returnSize; i++) {
printf("%s ", res[i]);
free(res[i]);
}
free(res);
return 0;
}Java
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
public class GfG {
// Function to return a list that contains all the generated letter combinations
public static List<String> letterCombinations(int[] a) {
// mp[i] stores all characters that correspond to ith digit in phone
String[] mp = { "0", "1", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz" };
// To store the generated letter combinations
List<String> res = new LinkedList<>();
// Queue to store intermediate combinations
Queue<String> q = new LinkedList<>();
q.add("");
// Process combinations using BFS-like approach
while (!q.isEmpty()) {
String s = q.poll();
// If complete word is generated, add to the result list
if (s.length() == a.length) {
res.add(s);
} else {
// Try all possible letters for the current digit in the vector a
String chars = mp[a[s.length()]];
for (char c : chars.toCharArray()) {
q.add(s + c);
}
}
}
return res;
}
// Driver code
public static void main(String[] args) {
int[] a = {2, 3};
List<String> res = letterCombinations(a);
for (String word : res) {
System.out.print(word + " ");
}
}
}Python
from collections import deque
# Function to return a list that contains all the generated letter combinations
def letter_combinations(a):
# mp[i] stores all characters that correspond to ith digit in phone
mp = ["0", "1", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"]
# To store the generated letter combinations
res = []
# Queue to store intermediate combinations
q = deque([""])
# Process combinations using BFS-like approach
while q:
s = q.popleft()
# If complete word is generated, add to the result list
if len(s) == len(a):
res.append(s)
else:
# Try all possible letters for the current digit in the vector a
chars = mp[a[len(s)]]
for c in chars:
q.append(s + c)
return res
# Driver code
a = [2, 3]
res = letter_combinations(a)
print(" ".join(res))JavaScript
// Function to return an array that contains all the generated letter combinations
function letterCombinations(a) {
// mp[i] stores all characters that correspond to ith digit in phone
const mp = ["0", "1", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"];
// To store the generated letter combinations
const res = [];
// Queue to store intermediate combinations
const q = [];
q.push("");
// Process combinations using BFS-like approach
while (q.length > 0) {
const s = q.shift();
// If complete word is generated, add to the result list
if (s.length === a.length) {
res.push(s);
} else {
// Try all possible letters for the current digit in the vector a
const chars = mp[a[s.length]];
for (const c of chars) {
q.push(s + c);
}
}
}
return res;
}
// Driver code
const a = [2, 3];
const res = letterCombinations(a);
console.log(res.join(" "));