En numérique, les claviers, les textes et les chiffres sont placés sur la même touche. Pour l'exemple 2, a "ABC" si nous voulions écrire tout ce qui commence par "A", nous avons besoin de taper la touche 2 une fois. Si nous voulions type "B", appuyez sur la touche 2 deux fois et trois fois pour écrire "C". ci-dessous est l'image d'un tel clavier.
![keypad]()
Compte tenu d'un clavier comme indiqué dans le schéma, et d'un n nombre de chiffre, de la liste de tous les mots qui sont possibles en appuyant sur ces chiffres.
Par exemple, si le numéro d'entrée est de 234, mots possibles qui peuvent être formés sont (par ordre Alphabétique):
adg adh adi aeg aeh aei afg afh, l'afi bdg bdh bdi beg beh bei bfg bfh bfi cdg cdh cdi ceg ceh cei cfg cfh fci
Nous allons faire quelques calculs en premier. Combien de mots sont possibles avec sept chiffres avec les chiffres représentant les n lettres? Pour le premier chiffre, nous avons tout au plus quatre choix, et pour chaque choix de la première lettre, nous avons tout au plus quatre choix pour le deuxième chiffre, et ainsi de suite. Il est donc simple de maths, il sera O(4^n). Depuis les touches 0 et 1 n'ont pas d'alphabet, et de nombreux personnages ont 3 personnages, 4^n serait à la limite supérieure du nombre de mots et le minimum de mots.
Maintenant, nous allons faire quelques exemples.
Pour le numéro ci-dessus 234. Voyez-vous de n'importe quel motif? Oui, nous remarquons que le dernier caractère toujours soit G,H ou I et à chaque fois qu'il remet à sa valeur de I à G, le chiffre à gauche de celle-ci est changé.
De la même façon à chaque fois que l'avant-dernière de l'alphabet réinitialise sa valeur, le troisième de la dernière de l'alphabet est modifiée et ainsi de suite. Premier caractère réinitialise une seule fois, lorsque nous avons généré tous les mots. Ceci peut être vu à partir de l'autre extrémité également. C'est-à-dire chaque fois que le caractère à la position i les changements, le caractère à la position i+1 passe par tous les caractères possibles et il crée l'effet d'entraînement jusqu'à nous rejoindre à la fin.
Puisque 0 et 1 n'ont pas de caractères qui leur sont associés. nous devons casser car il n'y aura pas d'itération pour ces chiffres.
Prenons la deuxième approche, comme il sera facile à mettre en œuvre en utilisant la récursivité. Nous allons jusqu'à la fin et revenir un par un. Parfait état pour la récursivité. nous allons chercher la base de cas.
Lorsque nous arrivons au dernier caractère, nous imprimons la parole avec tous les caractères possibles pour le dernier chiffre et le retour. Simple de la base de cas.Lorsque nous arrivons au dernier caractère, nous imprimons la parole avec tous les caractères possibles pour le dernier chiffre et le retour. Simple de la base de cas.
La suite C est de la mise en œuvre de l'approche récursive pour l'impression de tous les mots possibles correspondant à un n chiffres du numéro d'entrée. Noter que le nombre d'entrée est représenté comme un tableau pour simplifier le code.
#include <stdio.h>
#include <string.h>
// hashTable[i] stores all characters that correspond to digit i in phone
const char hashTable[10][5] = {"", "", "abc", "def", "ghi", "jkl",
"mno", "pqrs", "tuv", "wxyz"};
// A recursive function to print all possible words that can be obtained
// by input number[] of size n. The output words are one by one stored
// in output[]
void printWordsUtil(int number[], int curr_digit, char output[], int n)
{
// Base case, if current output word is prepared
int i;
if (curr_digit == n)
{
printf("%s ", output);
return ;
}
// Try all 3 possible characters for current digir in number[]
// and recur for remaining digits
for (i=0; i<strlen(hashTable[number[curr_digit]]); i++)
{
output[curr_digit] = hashTable[number[curr_digit]][i];
printWordsUtil(number, curr_digit+1, output, n);
if (number[curr_digit] == 0 || number[curr_digit] == 1)
return;
}
}
// A wrapper over printWordsUtil(). It creates an output array and
// calls printWordsUtil()
void printWords(int number[], int n)
{
char result[n+1];
result[n] ='\0';
printWordsUtil(number, 0, result, n);
}
//Driver program
int main(void)
{
int number[] = {2, 3, 4};
int n = sizeof(number)/sizeof(number[0]);
printWords(number, n);
return 0;
}
Sortie:
adg adh adi aeg aeh aei afg afh afi bdg bdh bdi beg beh bei bfg bfh bfi cdg cdh cdi ceg ceh cei cfg cfh cfi
Le Temps De La Complexité:
Le temps de la complexité de code ci-dessus est O(4^n) où n est le nombre de chiffres dans le numéro d'entrée.
Références:
http://www.flipkart.com/programming-interviews-exposed-secrets-landing-your-next-job-3rd/p/itmdxghumef3sdjn?pid=9788126539116&affid=sandeepgfg
