Dada una array de enteros que contiene dígitos de [0, 9] , la tarea es imprimir todas las combinaciones de letras posibles que los números podrían representar.
Se sigue un mapeo de dígitos a letras (igual que en los botones del teléfono). Tenga en cuenta que 0 y 1 no se asignan a ninguna letra. Todo el mapeo se muestra en la siguiente imagen:
Ejemplo:
Entrada: arr[] = {2, 3}
Salida: ad ae af bd be bf cd ce cfEntrada: arr[] = {9}
Salida: wxyz
Enfoque: Ahora pensemos cómo abordaríamos este problema sin hacerlo de manera iterativa. Una solución recursiva es intuitiva y común. Seguimos agregando cada letra posible recursivamente y esto generará todas las strings posibles.
Pensemos en cómo podemos construir una solución iterativa usando la recursiva. La recursividad es posible mediante el uso de una pila. Entonces, si usamos una pila en lugar de una función recursiva, ¿será una solución iterativa? Uno podría decirlo hablando técnicamente, pero en realidad no estamos haciendo nada diferente en términos de lógica.
Una pila es un LIFO DS. ¿Podemos usar otra estructura de datos? ¿Cuál será la diferencia si usamos un FIFO DS? Digamos una cola. Dado que BFS se realiza por cola y DFS por pila, ¿hay alguna diferencia entre los dos?
La diferencia entre DFS y BFS es similar a esta pregunta. En DFS encontraremos cada camino posible en el árbol uno por uno. Primero realizará todos los pasos para una ruta, mientras que BFS construirá todas las rutas juntas, un paso a la vez.
Entonces, una cola funcionaría perfectamente para esta pregunta. La única diferencia entre los dos algoritmos que usan cola y pila será la forma en que se forman. La pila formará todas las strings completamente una por una, mientras que la cola formará todas las strings juntas, es decir, después de x número de pases, todas las strings tendrán una longitud de x.
Por ejemplo:
If the given number is "23", then using queue, the letter combinations obtained will be: ["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"] and using stack, the letter combinations obtained will be: ["cf","ce","cd","bf","be","bd","af","ae","ad"].
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
// Function to return a vector that contains
// all the generated letter combinations
vector<string> letterCombinationsUtil(const int number[],
int n,
const string table[])
{
// To store the generated letter combinations
vector<string> list;
queue<string> q;
q.push("");
while (!q.empty()) {
string s = q.front();
q.pop();
// If complete word is generated
// push it in the list
if (s.length() == n)
list.push_back(s);
else
// Try all possible letters for current digit
// in number[]
for (auto letter : table[number[s.length()]])
q.push(s + letter);
}
// Return the generated list
return list;
}
// Function that creates the mapping and
// calls letterCombinationsUtil
void letterCombinations(const int number[], int n)
{
// table[i] stores all characters that
// corresponds to ith digit in phone
string table[10]
= { "0", "1", "abc", "def", "ghi",
"jkl", "mno", "pqrs", "tuv", "wxyz" };
vector<string> list
= letterCombinationsUtil(number, n, table);
// Print the contents of the vector
for (auto word : list)
cout << word << " ";
return;
}
// Driver code
int main()
{
int number[] = { 2, 3 };
int n = sizeof(number) / sizeof(number[0]);
// Function call
letterCombinations(number, n);
return 0;
}
Java
// Java implementation of the approach
import java.io.*;
import java.util.*;
class GFG {
// Function to return a vector that contains
// all the generated letter combinations
static ArrayList<String>
letterCombinationsUtil(int[] number, int n,
String[] table)
{
// To store the generated letter combinations
ArrayList<String> list = new ArrayList<>();
Queue<String> q = new LinkedList<>();
q.add("");
while (!q.isEmpty()) {
String s = q.remove();
// If complete word is generated
// push it in the list
if (s.length() == n)
list.add(s);
else {
String val = table[number[s.length()]];
for (int i = 0; i < val.length(); i++)
{
q.add(s + val.charAt(i));
}
}
}
return list;
}
// Function that creates the mapping and
// calls letterCombinationsUtil
static void letterCombinations(int[] number, int n)
{
// table[i] stores all characters that
// corresponds to ith digit in phone
String[] table
= { "0", "1", "abc", "def", "ghi",
"jkl", "mno", "pqrs", "tuv", "wxyz" };
ArrayList<String> list
= letterCombinationsUtil(number, n, table);
// Print the contents of the list
for (int i = 0; i < list.size(); i++) {
System.out.print(list.get(i) + " ");
}
}
// Driver code
public static void main(String args[])
{
int[] number = { 2, 3 };
int n = number.length;
// Function call
letterCombinations(number, n);
}
}
// This code is contributed by rachana soma
Python3
# Python3 implementation of the approach
from collections import deque
# Function to return a list that contains
# all the generated letter combinations
def letterCombinationsUtil(number, n, table):
list = []
q = deque()
q.append("")
while len(q) != 0:
s = q.pop()
# If complete word is generated
# push it in the list
if len(s) == n:
list.append(s)
else:
# Try all possible letters for current digit
# in number[]
for letter in table[number[len(s)]]:
q.append(s + letter)
# Return the generated list
return list
# Function that creates the mapping and
# calls letterCombinationsUtil
def letterCombinations(number, n):
# table[i] stores all characters that
# corresponds to ith digit in phone
table = ["0", "1", "abc", "def", "ghi", "jkl",
"mno", "pqrs", "tuv", "wxyz"]
list = letterCombinationsUtil(number, n, table)
s = ""
for word in list:
s += word + " "
print(s)
return
# Driver code
number = [2, 3]
n = len(number)
# Function call
letterCombinations(number, n)
C#
// C# implementation of the approach
using System;
using System.Collections.Generic;
class GFG {
// Function to return a vector that contains
// all the generated letter combinations
static List<String>
letterCombinationsUtil(int[] number, int n,
String[] table)
{
// To store the generated letter combinations
List<String> list = new List<String>();
Queue<String> q = new Queue<String>();
q.Enqueue("");
while (q.Count != 0) {
String s = q.Dequeue();
// If complete word is generated
// push it in the list
if (s.Length == n)
list.Add(s);
else {
String val = table[number[s.Length]];
for (int i = 0; i < val.Length; i++) {
q.Enqueue(s + val[i]);
}
}
}
return list;
}
// Function that creates the mapping and
// calls letterCombinationsUtil
static void letterCombinations(int[] number, int n)
{
// table[i] stores all characters that
// corresponds to ith digit in phone
String[] table
= { "0", "1", "abc", "def", "ghi",
"jkl", "mno", "pqrs", "tuv", "wxyz" };
List<String> list
= letterCombinationsUtil(number, n, table);
// Print the contents of the list
for (int i = 0; i < list.Count; i++) {
Console.Write(list[i] + " ");
}
}
// Driver code
public static void Main(String[] args)
{
int[] number = { 2, 3 };
int n = number.Length;
// Function call
letterCombinations(number, n);
}
}
// This code is contributed by Princi Singh
Javascript
</script>
function letterCombinations(digits) {
if(digits == ""){
return [];
}
let table = [ '0','1','abc','def','ghi','jkl','mno','pqrs','tuv','wxyz'];
let res =[];
let que = [''];
while(que.length>0){
let str = que[0];
que.shift();
if(str.length == digits.length){
res.push(str); // if all digits are replaced with char push to result
} else{
// get the current number from the digits i.e if str.length = 2 , digits =123 s= 3
let s= Number(digits.charAt(str.length));
let val = table[s]; // get char from the table i.e def for s =3
for(i=0;i<val.length;i++){
que.push(str+val.charAt(i));
}
}
}
return res;
}
// Driver code
let str = "23";
document.write(letterCombinations(str));
// This code is contributed by Niloy Biswas(niloy1995)
</script>
ad ae af bd be bf cd ce cf
Complejidad del Tiempo:
Espacio Auxiliar: O(4^n)