En nuestra vida diaria, tenemos que recordar muchos números de teléfono. A la mayoría de las personas les resulta bastante difícil recordar números de teléfono tan grandes de 10 dígitos. Una solución sencilla es relacionar ese número de teléfono con alguna palabra conocida.
Por ejemplo, podemos relacionar el número de teléfono 32627287 con DAMASCO en función de los caracteres de nuestro teclado de marcación. (Podemos reemplazar un DÍGITO con cualquiera del CARÁCTER correspondiente que representa en el teclado de marcación. Por ejemplo, tenemos ABC mencionado debajo de 2 en nuestro teclado de marcación. Entonces podemos representar 2 con A o B o C. De manera similar podemos reemplace 3 con D o E o F .
Escriba un programa que tome un número de teléfono e imprima todas las palabras posibles que están en nuestro diccionario.
Consideremos la entrada de muestra 23.
Aquí,
2 puede reemplazarse usando A, B o C.
3 puede reemplazarse usando D, E o F.
Entonces, una combinación válida sería AD, que corresponde a 623.
Otra puede ser CD, y así en.
Estamos generando todas las permutaciones posibles comenzando con {A o B o C} y luego {D o E o F}. Sin embargo, solo se imprimirán aquellas permutaciones que están en nuestro diccionario. Estas palabras seleccionadas representarán nuestro resultado de muestra.
Sin embargo, DIGITS como 1 y 0 serán reemplazados por una string nula ya que no representan ningún carácter en el teclado de marcación, es decir, 1 y 0 representarán «».
Ejemplos:
Input : 23 Output : [BE] Input : 623 Output : [MAD, OCD] Input : 726 Output : [PAN, PCM, PCO, RAM, SAM] Input : 2 Output : [A, B, C] Input : 123 Output : [BE]
.
Enfoque ingenuo
Este programa utiliza el retroceso para generar todas las palabras posibles. Haga clic aquí para obtener más información. El concepto de retroceso se ha explicado allí.
import java.util.*;
public class PhoneMnemonics {
static ArrayList<String> dictionary = new ArrayList<String>();
/* List all the phone mnemonics for the given digit sequence.
* @param input a digit sequence, like "23432" */
public static ArrayList<String> listMnemonics(String input)
{
ArrayList<String> list = new ArrayList<String>();
String[] dic = { "A", "B", "C", "D", "E", "F", "G",
"H", "I", "J", "K", "L", "M", "N",
"O", "P", "Q", "R", "S", "T", "U",
"V", "W", "X", "Y", "Z", "MAD",
"OCD", "PAN", "PCM", "PCO", "RAM", "SAM", "BE" };
for (String i : dic)
dictionary.add(i);
listMnemonics("", input, list);
return list;
}
/* Helper recursive method to list phone mnemonics. This works by finding
* all possibilities for the first digit, then recursing on the rest of the
* string. For example, if prefix is "AB" and remaining is "2", then the
* mnemonics "ABA", "ABB", and "ABC" would be printed.
*
* @param prefix : the part of the mnemonic that has already been built
* @param remaining : the remaining digits to include in the mnemonic */
private static void listMnemonics(String prefix, String remaining,
ArrayList<String> list)
{
// Base case: when there are no more characters to process,
// just print out the mnemonic that we've already built.
if (remaining.isEmpty()) {
if (!list.contains(prefix) && dictionary.contains(prefix))
list.add(prefix);
return;
}
// Recursive case.
if (remaining.charAt(0) == '1' || remaining.charAt(0) == '0') {
listMnemonics(prefix, remaining.substring(1), list);
}
String digits = digitLetters(remaining.charAt(0));
for (int i = 0; i < digits.length(); i++) {
String newPrefix = prefix + digits.charAt(i);
String newRemaining = remaining.substring(1);
listMnemonics(newPrefix, newRemaining, list);
}
}
/**
* Get the letters appearing on a given key of a standard phone keypad.
* @param ch the character representation of a digit on the phone keypad
* (like '2')
* @return a string containing the letters on the given key, or the empty
* string if the key is not recognized
*/
private static String digitLetters(char ch)
{
switch (ch) {
case '2':
return "ABC";
case '3':
return "DEF";
case '4':
return "GHI";
case '5':
return "JKL";
case '6':
return "MNO";
case '7':
return "PQRS";
case '8':
return "TUV";
case '9':
return "WXYZ";
}
return "";
}
public static void main(String[] args)
{
String str = "123";
ArrayList<String> list = listMnemonics(str);
System.out.println(list);
}
}
[BE]
Nota: Este programa será más conveniente para los usuarios una vez que agreguemos un diccionario de palabras junto con su frecuencia de uso. Usando un diccionario, la siguiente salida podría haberse optimizado para imprimir MAD, OCD, etc., en función de su frecuencia de uso. uso por parte de los usuarios. Echa un vistazo a este enlace: https://phonespell.org/ .
Artículo relacionado con la implementación de C++: imprima todas las palabras posibles de los dígitos del teléfono
Referencia:
Thinking Recursively por Eric Roberts .