Comment puis-je imprimer tous les possibles combinaisons de lettres un numéro de téléphone peut représenter?

Il est semblable à un question appelé les combinaisons de lettres d'un numéro de téléphone,
voici ma solution.

Cela fonctionne pour un nombre arbitraire de chiffres, tant que le résultat ne dépasse pas la limite de la mémoire.

import java.util.HashMap;
public class Solution {
    public ArrayList<String> letterCombinations(String digits) {
        ArrayList<String> res = new ArrayList<String>();
        ArrayList<String> preres = new ArrayList<String>();
        res.add("");

        for(int i = 0; i < digits.length(); i++) {
            String letters = map.get(digits.charAt(i));
            if (letters.length() == 0)
                continue;
            for(String str : res) {
                for(int j = 0; j < letters.length(); j++)
                    preres.add(str + letters.charAt(j));
            }
            res = preres;
            preres = new ArrayList<String>();
        }      
        return res;
    }

    static final HashMap<Character,String> map = new HashMap<Character,String>(){{
        put('1', "");
        put('2',"abc");
        put('3',"def");
        put('4',"ghi");
        put('5',"jkl");
        put('6',"mno");
        put('7',"pqrs");
        put('8',"tuv");
        put('9',"wxyz");
        put('0', "");
    }} ;
}

Je ne suis pas sûr de savoir comment à 12 chiffres des numéros internationaux influent sur la conception.

Edit: numéros Internationaux seront également traitées

La solution la plus évidente est une fonction de la carte un chiffre à une liste de clés, puis une fonction qui permettrait de générer les combinaisons possibles:

La première est évidente, la seconde est plus problématique parce que vous avez autour de 3^nombre de combinaisons de chiffres, qui peuvent être d'un très grand nombre.

Une façon de le faire est de regarder à chaque possibilité, pour les chiffres correspondants pour un chiffre dans un nombre (sur la base de 4) et de mettre en œuvre quelque chose de proche d'un compteur (saut à plus de certains cas, car il y a généralement moins de 4 lettres transposable à un chiffre).

La plus évidente des solutions serait de boucles imbriquées ou la récursivité, qui sont à la fois moins élégant, mais à mon avis valable.

Une autre chose pour laquelle il faut prendre soin de est pour éviter les problèmes d'échelle (par exemple en gardant les possibilités de la mémoire, etc.) puisque nous parlons de beaucoup de combinaisons.

P. S. une Autre extension intéressante de la question de la localisation.

Numérique des claviers, des textes et des nombres 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.

clavier http://d2o58evtke57tz.cloudfront.net/wp-content/uploads/phoneKeyboard.png

Donné 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 nombre au-dessus de 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.

Suivant est C 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] ='
#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;
}
';
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;
}

De 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

Complexité Temporelle:

Temps de 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

Ce problème est similaire à cette leetcode problème. Voici la réponse que j'ai soumis ce problème à leetcode (vérifier github et vidéo pour l'explication).

De sorte que la première chose dont nous avons besoin est une certaine façon de tenir les mappages d'un chiffre et on peut utiliser une carte pour ce:

private Map<Integer, String> getDigitMap() {
        return Stream.of(
                new AbstractMap.SimpleEntry<>(2, "abc"),
                new AbstractMap.SimpleEntry<>(3, "def"),
                new AbstractMap.SimpleEntry<>(4, "ghi"),
                new AbstractMap.SimpleEntry<>(5, "jkl"),
                new AbstractMap.SimpleEntry<>(6, "mno"),
                new AbstractMap.SimpleEntry<>(7, "pqrs"),
                new AbstractMap.SimpleEntry<>(8, "tuv"),
                new AbstractMap.SimpleEntry<>(9, "wxyz"))
               .collect(Collectors.toMap(AbstractMap.SimpleEntry::getKey, 
                                AbstractMap.SimpleEntry::getValue));
}

La méthode ci-dessus est la préparation de la carte et de la méthode suivante je voudrais utiliser est de fournir à la cartographie, à condition chiffres:

private String getDigitMappings(String strDigit, Map<Integer,String> digitMap) {
        int digit = Integer.valueOf(strDigit);
        return digitMap.containsKey(digit) ? digitMap.get(digit) : "";
}

Ce problème peut être résolu à l'aide de revenir en arrière et un recul de la solution a généralement une structure où la signature de la méthode contiendra: conteneur de résultat, temp résultats, la source d'origine avec index etc. Si la méthode que la structure pourrait être de la forme:

private void compute(List<String> result, StringBuilder temp, String digits, int start, Map<Integer, String> digitMap) {
       //Condition to populate temp value to result
       //explore other arrangements based on the next input digit
       //Loop around the mappings of a digit and then to explore invoke the same method recursively
       //Also need to remove the digit which was in temp at last so as to get proper value in temp for next cycle in loop
}

Et maintenant le corps de la méthode peut être rempli aussi (résultat sera conservé dans une liste, la température dans le générateur de chaîne, etc.)

private void compute(List<String> result, StringBuilder temp, String digits, int start, Map<Integer, String> digitMap) {
        if(start >= digits.length()) { //condition
            result.add(temp.toString());
            return;
        }

        String letters = getDigitMappings(digits.substring(start, start + 1), digitMap); //mappings of a digit to loop around
        for (int i = 0; i < letters.length(); i++) {
            temp.append(letters.charAt(i));
            compute(result, temp, digits, start+1, digitMap); //explore for remaining digits
            temp.deleteCharAt(temp.length() - 1); //remove last in temp
        }
}

Et, enfin, la méthode peut être invoquée comme:

public List<String> letterCombinations(String digits) {
        List<String> result = new ArrayList<>();
        if(digits == null || digits.length() == 0) return result;
        compute(result, new StringBuilder(), digits, 0, getDigitMap());
        return result;
}

Maintenant le max mappé caractères pour un chiffre peut-être 4 (par exemple, 9 wxyz) et les retours en arrière implique une recherche exhaustive pour explorer tous les arrangements possibles (espace d'état de l'arbre) donc pour un chiffre de taille n nous allons avoir 4x4x4....n times c'est à dire la complexité serait O(4^n).

Utiliser une liste L où L[i] = les symboles que les chiffres que je peux représenter.

L[1] = @,.,! (pour exemple)
L[2] = a,b,c

Etc.

Ensuite, vous pouvez faire quelque chose comme ceci (pseudo-C):

void f(int k, int st[])
{
  if ( k > numberOfDigits )
  {
    print contents of st[];
    return;
  }

  for each character c in L[Digit At Position k]
  {
    st[k] = c;
    f(k + 1, st);
  }
}

En supposant que chaque liste contient 3 personnages, nous avons 3^7 possibilités de 7 chiffres et 3^12 pour 12, ce qui n'est pas beaucoup. Si vous avez besoin de toutes les combinaisons, je ne vois pas beaucoup mieux. Vous pouvez éviter la récursivité et autres joyeusetés, mais vous n'allez pas pour obtenir quelque chose de beaucoup plus rapide que ce n'importe quoi.

Vous trouvez la source (Scala) ici et un travail applet ici.

Depuis 0 et 1 ne sont pas associés à des caractères, ils construisent naturel des points d'arrêt dans les nombres. Mais ils ne surviennent pas dans chaque numéro (à l'exception de 0 au début). Plus de tels chiffres +49567892345 de 9 chiffres commençant, peut conduire à OutOfMemoryErrors. Il serait donc préférable de diviser un nombre dans des groupes comme

• 01723 5864
• 0172 35864

de voir, si vous pouvez faire sens à partir de la plus courte des parties. J'ai écrit un tel programme, et testé certains nombres de mes amis, mais trouve rarement des combinaisons de mots plus courts, ce qui peut être vérifié dans le dictionnaire pour la correspondance, pour ne pas mentionner unique, les mots longs.

Donc, ma décision a été de seulement de faciliter la recherche,, pas d'automatisation complète, par l'affichage de combinaisons possibles, en encourageant le fractionnement du nombre par la main, peut-être plusieurs fois.

J'ai donc trouvé +-RAD JUNG (+-vélo garçon).

Si vous acceptez les fautes d'orthographe, les abréviations, les mots étrangers, les numéros que des mots, des nombres en mots, et les noms, vos chances de trouver une solution est beaucoup mieux, que sans bidouiller.

246848 => 2hot4u (too hot for you) 
466368 => goodn8 (good night) 
1325   => 1FCK   (Football club)
53517  => JDK17  (Java Developer Kit)

sont des choses qu'un humain peut observer à faire un algorithme de trouver de telles choses, c'est plutôt dur.

Un Python solution est très économique, et parce qu'il utilise des générateurs est efficace en termes d'utilisation de la mémoire.

import itertools

keys = dict(enumerate('::ABC:DEF:GHI:JKL:MNO:PQRS:TUV:WXYZ'.split(':')))

def words(number):
    digits = map(int, str(number))
    for ls in itertools.product(*map(keys.get, digits)):
        yield ''.join(ls)

for w in words(258):
    print w

Évidemment itertools.product est de résoudre le problème pour vous. Mais l'écriture de soi-même n'est pas difficile. Voici une solution en aller, ce qui est prudent de les ré-utiliser le tableau result pour générer toutes les solutions, et d'une fermeture f pour capturer le générés les mots. Combinés, ces donner O(log n) l'utilisation de la mémoire à l'intérieur de product.

package main

import (
    "bytes"
    "fmt"
    "strconv"
)

func product(choices [][]byte, result []byte, i int, f func([]byte)) {
    if i == len(result) {
        f(result)
        return
    }
    for _, c := range choices[i] {
        result[i] = c
        product(choices, result, i+1, f)
    }
}

var keys = bytes.Split([]byte("::ABC:DEF:GHI:JKL:MNO:PQRS:TUV:WXYZ"), []byte(":"))

func words(num int, f func([]byte)) {
    ch := [][]byte{}
    for _, b := range strconv.Itoa(num) {
        ch = append(ch, keys[b-'0'])
    }
    product(ch, make([]byte, len(ch)), 0, f)
}

func main() {
    words(256, func(b []byte) { fmt.Println(string(b)) })
}

Cette version en C# est relativement efficace, et cela fonctionne pour les non-ouest de chiffres (comme les "۱۲۳۴۵۶۷" par exemple).

static void Main(string[] args)
{
    string phoneNumber = null;
    if (1 <= args.Length)
        phoneNumber = args[0];
    if (string.IsNullOrEmpty(phoneNumber))
    {
        Console.WriteLine("No phone number supplied.");
        return;
    }
    else
    {
        Console.WriteLine("Alphabetic phone numbers for \"{0}\":", phoneNumber);
        foreach (string phoneNumberText in GetPhoneNumberCombos(phoneNumber))
            Console.Write("{0}\t", phoneNumberText);
    }
}

public static IEnumerable<string> GetPhoneNumberCombos(string phoneNumber)
{
    phoneNumber = RemoveNondigits(phoneNumber);
    if (string.IsNullOrEmpty(phoneNumber))
        return new List<string>();

    char[] combo = new char[phoneNumber.Length];
    return GetRemainingPhoneNumberCombos(phoneNumber, combo, 0);
}

private static string RemoveNondigits(string phoneNumber)
{
    if (phoneNumber == null)
        return null;
    StringBuilder sb = new StringBuilder();
    foreach (char nextChar in phoneNumber)
        if (char.IsDigit(nextChar))
            sb.Append(nextChar);
    return sb.ToString();
}

private static IEnumerable<string> GetRemainingPhoneNumberCombos(string phoneNumber, char[] combo, int nextDigitIndex)
{
    if (combo.Length - 1 == nextDigitIndex)
    {
        foreach (char nextLetter in phoneNumberAlphaMapping[(int)char.GetNumericValue(phoneNumber[nextDigitIndex])])
        {
            combo[nextDigitIndex] = nextLetter;
            yield return new string(combo);
        }
    }
    else
    {
        foreach (char nextLetter in phoneNumberAlphaMapping[(int)char.GetNumericValue(phoneNumber[nextDigitIndex])])
        {
            combo[nextDigitIndex] = nextLetter;
            foreach (string result in GetRemainingPhoneNumberCombos(phoneNumber, combo, nextDigitIndex + 1))
                yield return result;
        }
    }

}

private static char[][] phoneNumberAlphaMapping = new char[][]
{
    new char[] { '0' },
    new char[] { '1' },
    new char[] { 'a', 'b', 'c' },
    new char[] { 'd', 'e', 'f' },
    new char[] { 'g', 'h', 'i' },
    new char[] { 'j', 'k', 'l' },
    new char[] { 'm', 'n', 'o' },
    new char[] { 'p', 'q', 'r', 's' },
    new char[] { 't', 'u', 'v' },
    new char[] { 'w', 'x', 'y', 'z' }
};

Ici est celui de la douleur C. celui-ci est likley pas efficet (en fait, je ne pense pas que c'est à tous). Mais il y a quelques intresting aspects.

1. De prendre un numéro et la convertit en une chaîne de
2. Il soulève le nombre de graines chaque fois pour créer la prochaine chaîne séquentielle

Ce qui est agréable, c'est qu'il n'y a pas vraiment de limite à la taille de la chaîne (pas de limite de caractères) Cela vous permet de générer de plus en plus longues chaînes si besoin est juste en attendant.

#include <stdlib.h>
#include <stdio.h>

#define CHARACTER_RANGE 95  // The range of valid password characters
#define CHARACTER_OFFSET 32 // The offset of the first valid character

void main(int argc, char *argv[], char *env[])
{
    int i;

    long int string;
    long int worker;
    char *guess;    // Current Generation
    guess = (char*)malloc(1);   // Allocate it so free doesn't fail

    int cur;

    for ( string = 0; ; string++ )
    {
        worker = string;

        free(guess);
        guess = (char*)malloc((string/CHARACTER_RANGE+1)*sizeof(char)); // Alocate for the number of characters we will need

        for ( i = 0; worker > 0 && i < string/CHARACTER_RANGE + 1; i++ )    // Work out the string
        {
            cur = worker % CHARACTER_RANGE; // Take off the last digit
            worker = (worker - cur) /CHARACTER_RANGE;  // Advance the digits
            cur += CHARACTER_OFFSET;

            guess[i] = cur;
        }
        guess[i+1] = '
#include <stdlib.h>
#include <stdio.h>
#define CHARACTER_RANGE 95  // The range of valid password characters
#define CHARACTER_OFFSET 32 // The offset of the first valid character
void main(int argc, char *argv[], char *env[])
{
int i;
long int string;
long int worker;
char *guess;    // Current Generation
guess = (char*)malloc(1);   // Allocate it so free doesn't fail
int cur;
for ( string = 0; ; string++ )
{
worker = string;
free(guess);
guess = (char*)malloc((string/CHARACTER_RANGE+1)*sizeof(char)); // Alocate for the number of characters we will need
for ( i = 0; worker > 0 && i < string/CHARACTER_RANGE + 1; i++ )    // Work out the string
{
cur = worker % CHARACTER_RANGE; // Take off the last digit
worker = (worker - cur) /CHARACTER_RANGE;  // Advance the digits
cur += CHARACTER_OFFSET;
guess[i] = cur;
}
guess[i+1] = '\0';  // NULL terminate our string
printf("%s\t%d\n", guess, string);
}
}
';  // NULL terminate our string

        printf("%s\t%d\n", guess, string);
    }
}

/**
 * Simple Java implementation without any input/error checking 
 * (expects all digits as input)
 **/
public class PhoneSpeller
{

    private static final char[][] _letters = new char[][]{
            {'0'},
            {'1'},
            {'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'}
    };

    public static void main(String[] args)
    {
        if (args.length != 1)
        {
            System.out.println("Please run again with your phone number (no dashes)");
            System.exit(0);
        }
        recursive_phoneSpell(args[0], 0, new ArrayList<String>());

    }


    private static void recursive_phoneSpell(String arg, int index, List<String> results)
    {
        if (index == arg.length())
        {
            printResults(results);
            return;
        }
        int num = Integer.parseInt(arg.charAt(index)+"");

        if (index==0)
        {
            for (int j = 0; j<_letters[num].length; j++)
            {
                results.add(_letters[num][j]+"");
            }
            recursive_phoneSpell(arg, index+1, results);
        }
        else
        {
            List<String> combos = new ArrayList<String>();
            for (int j = 0; j<_letters[num].length; j++)
            {
                 for (String result : results)
                 {
                     combos.add(result+_letters[num][j]);
                 }
            }
            recursive_phoneSpell(arg, index+1, combos);
        }
    }

    private static void printResults(List<String> results)
    {
        for (String result : results)
        {
            System.out.println(result);
        }
    }
}

Voici le code de travail pour le même..
son un la récursivité sur chaque étape de vérification de la possibilité pour chacun des combinaisons sur la présence des mêmes chiffres dans une série....Je ne suis pas sûr si il y a une meilleure solution, alors cette complexité point de vue.....

S'il vous plaît laissez-moi savoir pour tous les problèmes....

import java.util.ArrayList;


public class phonenumbers {

    /**
     * @param args
     */
    public static String mappings[][] = {
        {"0"}, {"1"}, {"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"}
    };

    public static void main(String[] args) {
        //TODO Auto-generated method stub

        String phone = "3333456789";
        ArrayList<String> list= generateAllnums(phone,"",0);
    }

    private static ArrayList<String> generateAllnums(String phone,String sofar,int j) {
        //TODO Auto-generated method stub

        //System.out.println(phone);
        if(phone.isEmpty()){
            System.out.println(sofar);
            for(int k1=0;k1<sofar.length();k1++){
                int m=sofar.toLowerCase().charAt(k1)-48;
                if(m==-16)
                    continue;
                int i=k1;
                while(true && i<sofar.length()-2){
                    if(sofar.charAt(i+1)==' ')
                        break;
                    else if(sofar.charAt(i+1)==sofar.charAt(k1)){
                        i++;
                    }else{
                        break;
                    }

                }
                i=i-k1;
                //System.out.print(" " + m +", " + i + " ");
                System.out.print(mappings[m][i%3]);
                k1=k1+i;
            }
            System.out.println();

            return null;
        }
        int num= phone.charAt(j);
        int k=0;
        for(int i=j+1;i<phone.length();i++){
            if(phone.charAt(i)==num){
                k++;
            }
        }

        if(k!=0){

            int p=0;
            ArrayList<String> list2= generateAllnums(phone.substring(p+1), sofar+phone.charAt(p)+ " ", 0);
            ArrayList<String> list3= generateAllnums(phone.substring(p+1), sofar+phone.charAt(p), 0);

        }
        else{
            ArrayList<String> list1= generateAllnums(phone.substring(1), sofar+phone.charAt(0), 0);
        }
        return null;

    }

}

J'ai réécrit la dernière réponse à cette (visées ci-dessus) , de C à Java. J'ai aussi inclus le support pour les 0 et 1 (0 et 1) parce que les nombres tels que 555-5055 ne fonctionnaient pas du tout avec le code ci-dessus.

C'est ici. Certains commentaires sont conservés.

public static void printPhoneWords(int[] number) {
    char[] output = new char[number.length];
    printWordsUtil(number,0,output);
}

static String[] phoneKeys= new String[]{"0", "1", "ABC", "DEF", "GHI", "JKL",
               "MNO", "PQRS", "TUV", "WXYZ"};
private static void printWordsUtil(int[] number, int curDigIndex, char[] output) {
    //Base case, if current output word is done
    if (curDigIndex == output.length) {
        System.out.print(String.valueOf(output) + " "); 
        return;
    }

      //Try all 3-4 possible characters for the current digit in number[]
      //and recurse for the remaining digits

    char curPhoneKey[] = phoneKeys[number[curDigIndex]].toCharArray();
    for (int i = 0; i< curPhoneKey.length ; i++) {
        output[curDigIndex] = curPhoneKey[i];
        printWordsUtil(number, curDigIndex+1, output);
        if (number[curDigIndex] <= 1) //for 0 or 1
            return;
    }
}

public static void main(String[] args) {
    int number[] = {2, 3, 4};
    printPhoneWords(number);
    System.out.println();
}

Une option en Objective-C:

- (NSArray *)lettersForNumber:(NSNumber *)number {
    switch ([number intValue]) {
        case 2:
            return @[@"A",@"B",@"C"];
        case 3:
            return @[@"D",@"E",@"F"];
        case 4:
            return @[@"G",@"H",@"I"];
        case 5:
            return @[@"J",@"K",@"L"];
        case 6:
            return @[@"M",@"N",@"O"];
        case 7:
            return @[@"P",@"Q",@"R",@"S"];
        case 8:
            return @[@"T",@"U",@"V"];
        case 9:
            return @[@"W",@"X",@"Y",@"Z"];
        default:
            return nil;
    }
}

- (NSArray *)letterCombinationsForNumbers:(NSArray *)numbers {
    NSMutableArray *combinations = [[NSMutableArray alloc] initWithObjects:@"", nil];

    for (NSNumber *number in numbers) {
        NSArray *lettersNumber = [self lettersForNumber:number];

        //Ignore numbers that don't have associated letters
        if (lettersNumber.count == 0) {
            continue;
        }

        NSMutableArray *currentCombinations = [combinations mutableCopy];
        combinations = [[NSMutableArray alloc] init];

        for (NSString *letter in lettersNumber) {

            for (NSString *letterInResult in currentCombinations) {

                NSString *newString = [NSString stringWithFormat:@"%@%@", letterInResult, letter];
                [combinations addObject:newString];
            }
        }
    }

    return combinations;
}




InformationsquelleAutor Adriana

Une R solution à l'aide de boucles imbriquées:

# Create phone pad
two <- c("A", "B", "C")
three <- c("D", "E", "F")
four <- c("G", "H", "I")
five <- c("J", "K", "L")
six <- c("M", "N", "O", "P")
seven <- c("Q", "R", "S")
eight <- c("T", "U", "V")
nine <- c("W", "X", "Y", "Z")

# Choose three numbers
number_1 <- two
number_2 <- three
number_3 <- six

# create an object to save the combinations to
combinations <- NULL

# Loop through the letters in number_1
for(i in number_1){

    # Loop through the letters in number_2
    for(j in number_2){

        # Loop through the letters in number_3
        for(k in number_3){

                # Add each of the letters to the combinations object
                combinations <- c(combinations, paste0(i, j, k)) 

        }

    }

}

# Print all of the possible combinations
combinations

J'ai posté un autre, plus bizarre R solution à l'aide de plus de boucles et d'échantillonnage sur mon blog.

Scala solution:

def mnemonics(phoneNum: String, dict: IndexedSeq[String]): Iterable[String] = {
  def mnemonics(d: Int, prefix: String): Seq[String] = {
    if (d >= phoneNum.length) {
      Seq(prefix)
    } else {
      for {
        ch <- dict(phoneNum.charAt(d).asDigit)
        num <- mnemonics(d + 1, s"$prefix$ch")
      } yield num
    }
  }

  mnemonics(0, "")
}

En supposant que chaque chiffre cartes à plus de 4 caractères, le nombre d'appels récursifs T satisfaire l'inégalité T(n) <= 4T(n-1), qui est de l'ordre 4^n.

Au cours d'une entrevue d'emploi, j'ai reçu cette question de la création d'un tableau et l'impression de tous les possibles combinaisons de lettres d'un numéro de téléphone. Au cours de l'entrevue, j'ai reçu un murmure de mon interviewer au sujet de la récursivité et comment il ne peut pas être fait à l'aide de boucles. Très naturelle pour moi de recevoir des commentaires d'un autre programmeur, j'ai fait confiance à ses conseils au lieu de ma propre scolarité et procédé à écrire un sloppy la récursivité mess. Ça ne va pas si bien. Avant de recevoir de l'entrée, que je n'avais jamais reçu ce problème avant, mon cerveau était en train de calculer le sous-jacent reproductibles formule mathématique. Les chuchotements sous mon souffle, "ne peut pas il suffit de multiplier par trois, certains d'entre eux sont quatre" mon esprit a commencé la compétition à l'encontre d'un court horloge de penser à une réponse tout en commençant à écrire un autre. Il n'était pas jusqu'à la fin de la semaine, j'ai reçu mon appel pour me dire que le triste nouvelle. C'était plus tard dans la nuit, j'ai décidé de voir si c'est vraiment un problème de récursivité. S'avère pour moi il ne l'est pas.

Ma solution ci-dessous est codé en PHP, est non récursif, fonctionne avec n'importe quelle longueur de l'entrée et je l'ai même inclus quelques commentaires pour aider à décrire ce que mes noms de variables. Sa ma officiel et immuable réponse définitive à cette question. J'espère que cela aide quelqu'un d'autre dans l'avenir, n'hésitez pas à le traduire dans d'autres langues.

M'méthode consiste à calculer le nombre total de combinaisons et de la création d'un tampon assez grand pour contenir tous les octets. La longueur de mon tampon est de la même longueur que vous vous attendez à recevoir d'un algorithme récursif. Je fais un tableau qui contient les groupes de lettres qui représentent chaque numéro. Ma méthode fonctionne principalement parce que votre combo total sera toujours divisible par le nombre de lettres dans le groupe actuel. Si vous pouvez imaginer dans votre tête une liste verticale de la sortie de cet algorithme, ou voir la liste à la verticale, par opposition à l'horizontale avec une liste écrite des combinaisons, mon algorithme va commencer à faire sens. Cet algorithme nous permet de parcourir chaque octet verticalement de haut en bas en partant de la gauche, au lieu d'horizontalement de gauche à droite, et de remplir chaque octet individuellement, sans exiger de la récursivité. J'utilise le tampon comme si son un tableau d'octets pour gagner du temps et de l'énergie.

---

NON-RÉCURSIF ET ITÉRATIF PHP

<?php

//Display all possible combinations of letters for each number.

$input = '23456789';

//====================

if(!isset($input[0]))
    die('Nothing to see here!');

$phone_letters = array(
    2 => array('a', 'b', 'c'),
    3 => array('d', 'e', 'f'),
    4 => array('g', 'h', 'i'),
    5 => array('j', 'k', 'l'),
    6 => array('m', 'n', 'o'),
    7 => array('p', 'q', 'r', 's'),
    8 => array('t', 'u', 'v'),
    9 => array('w', 'x', 'y', 'z')
);

$groups = array();
$combos_total = 1;
$l = strlen($input);
for($i = 0; $i < $l; ++$i) {
    $groups[] = $phone_letters[$input[$i]];
    $combos_total *= count($phone_letters[$input[$i]]);
}
$count = $combos_total /count($groups[0]);
$combos = array_fill(0, $combos_total, str_repeat(chr(0), strlen($input)));

for(
    $group = 0,                     //Index for the current group of letters.
    $groups_count = count($groups), //Total number of letter groups.
    $letters = count($groups[0]),   //Total number of letters in the current group.
    $width = $combos_total,         //Number of bytes to repeat the current letter.
    $repeat = 1;                    //Total number of times the group will repeat.
    ;
) {
    for($byte = 0, $width /= $letters, $r = 0; $r < $repeat; ++$r)
        for($l = 0; $l < $letters; ++$l)
            for($w = 0; $w < $width; ++$w)
                $combos[$byte++][$group] = $groups[$group][$l];

    if(++$group < $groups_count) {
        $repeat *= $letters;
        $letters = count($groups[$group]);
    }
    else
        break;
}

//==================== 


if(is_array($combos)) {
    print_r($combos);
    echo 'Total combos:', count($combos), "\n";
}
else
    echo 'No combos.', "\n";
echo 'Expected combos: ', $combos_total, "\n";

---

NON-RÉCURSIVE, NON ITÉRATIF, PAS DE TAMPON, FIL AMICAL, LES MATHÉMATIQUES SEULEMENT + NON-RÉCURSIF ET ITÉRATIF PHP OBJET À L'AIDE DE MULTI-BASE BIG ENDIAN

Alors que je travaillais sur la nouvelle maison, l'autre jour, j'ai eu une prise de conscience que je pouvais utiliser les mathématiques à partir de ma première fonction couplé avec mes connaissances de base pour traiter tous les possibles combinaisons de lettres de mon entrée comme un multi-dimensionnelle nombre.

Mon objet fournit les fonctions nécessaires pour stocker une combinaison préférée dans une base de données, convertir les lettres et les chiffres, si c'était nécessaire, choisir une combinaison de n'importe où dans la combinaison de l'espace à l'aide d'une combinaison préférée ou octet et il joue très bien avec le multi-threading.

Cela étant dit, à l'aide de mon objet, je peux fournir une deuxième réponse qui utilise la base, pas de tampon, pas d'itérations et surtout pas de récursivité.

<?php
class phone {
public static $letters = array(
2 => array('a', 'b', 'c'),
3 => array('d', 'e', 'f'),
4 => array('g', 'h', 'i'),
5 => array('j', 'k', 'l'),
6 => array('m', 'n', 'o'),
7 => array('p', 'q', 'r', 's'),
8 => array('t', 'u', 'v'),
9 => array('w', 'x', 'y', 'z')
);
//Convert a letter into its respective number.
public static function letter_number($letter) {
if(!isset($letter[0]) || isset($letter[1]))
return false;
for($i = 2; $i < 10; ++$i)
if(in_array($letter, phone::$letters[$i], true))
return $i;
return false;
}
//Convert letters into their respective numbers.
public static function letters_numbers($letters) {
if(!isset($letters[0]))
return false;
$length = strlen($letters);
$numbers = str_repeat(chr(0), $length);
for($i = 0; $i < $length; ++$i) {
for($j = 2; $j < 10; ++$j) {
if(in_array($letters[$i], phone::$letters[$j], true)) {
$numbers[$i] = $j;
break;
}
}
}
return $numbers;
}
//Calculate the maximum number of combinations that could occur within a particular input size.
public static function combination_size($groups) {
return $groups <= 0 ? false : pow(4, $groups);
}
//Calculate the minimum bytes reqired to store a group using the current input.
public static function combination_bytes($groups) {
if($groups <= 0)
return false;
$size = $groups * 4;
$bytes = 0;
while($groups !== 0) {
$groups >> 8;
++$bytes;
}
return $bytes;
}
public $input = '';
public $input_len = 0;
public $combinations_total = 0;
public $combinations_length = 0;
private $iterations = array();
private $branches = array();
function __construct($number) {
if(!isset($number[0]))
return false;
$this->input = $number;
$input_len = strlen($number);
$combinations_total = 1;
for($i = 0; $i < $input_len; ++$i) {
$combinations_total *= count(phone::$letters[$number[$i]]);
}
$this->input_len = $input_len;
$this->combinations_total = $combinations_total;
$this->combinations_length = $combinations_total * $input_len;
for($i = 0; $i < $input_len; ++$i) {
$this->branches[] = $this->combination_branches($i);
$this->iterations[] = $this->combination_iteration($i);
}
}
//Calculate a particular combination in the combination space and return the details of that combination.
public function combination($combination) {
$position = $combination * $this->input_len;
if($position < 0 || $position >= $this->combinations_length)
return false;
$group = $position % $this->input_len;
$first = $position - $group;
$last = $first + $this->input_len - 1;
$combination = floor(($last + 1) /$this->input_len) - 1;
$bytes = str_repeat(chr(0), $this->input_len);
for($i = 0; $i < $this->input_len; ++$i)
$bytes[$i] = phone::$letters[$this->input[$i]][($combination /$this->branches[$i]) % count(phone::$letters[$this->input[$i]])];
return array(
'combination' => $combination,
'branches' => $this->branches[$group],
'iterations' => $this->iterations[$group],
'first' => $first,
'last' => $last,
'bytes' => $bytes
);
}
//Calculate a particular byte in the combination space and return the details of that byte.
public function combination_position($position) {
if($position < 0 || $position >= $this->combinations_length)
return false;
$group = $position % $this->input_len;
$group_count = count(phone::$letters[$this->input[$group]]);
$first = $position - $group;
$last = $first + $this->input_len - 1;
$combination = floor(($last + 1) /$this->input_len) - 1;
$index = ($combination /$this->branches[$group]) % $group_count;
$bytes = str_repeat(chr(0), $this->input_len);
for($i = 0; $i < $this->input_len; ++$i)
$bytes[$i] = phone::$letters[$this->input[$i]][($combination /$this->branches[$i]) % count(phone::$letters[$this->input[$i]])];
return array(
'position' => $position,
'combination' => $combination - 1,
'group' => $group,
'group_count' => $group_count,
'group_index' => $index,
'number' => $this->input[$group],
'branches' => $this->branches[$group],
'iterations' => $this->iterations[$group],
'first' => $first,
'last' => $last,
'byte' => phone::$letters[$this->input[$group]][$index],
'bytes' => $bytes
);
}
//Convert letters into a combination number using Multi-Base Big Endian.
public function combination_letters($letters) {
if(!isset($letters[$this->input_len - 1]) || isset($letters[$this->input_len]))
return false;
$combination = 0;
for($byte = 0; $byte < $this->input_len; ++$byte) {
$base = count(phone::$letters[$this->input[$byte]]);
$found = false;
for($value = 0; $value < $base; ++$value) {
if($letters[$byte] === phone::$letters[$this->input[$byte]][$value]) {
$combination += $value * $this->branches[$byte];
$found = true;
break;
}
}
if($found === false)
return false;
}
return $combination;
}
//Calculate the number of branches after a particular group.
public function combination_branches($group) {
if($group >= 0 && ++$group < $this->input_len) {
$branches = 1;
for($i = $group; $i < $this->input_len; ++$i)
$branches *= count(phone::$letters[$this->input[$i]]);
return $branches === 1 ? 1 : $branches;
}
elseif($group === $this->input_len)
return 1;
else
return false;   
}
//Calculate the number of iterations before a particular group.
public function combination_iteration($group) {
if($group > 0 && $group < $this->input_len) {
$iterations = 1;
for($i = $group - 1; $i >= 0; --$i)
$iterations *= count(phone::$letters[$this->input[$i]]);
return $iterations;
}
elseif($group === 0)
return 1;
else
return false;
}
//Iterations, Outputs array of all combinations using a buffer.
public function combinations() {
$count = $this->combinations_total /count(phone::$letters[$this->input[0]]);
$combinations = array_fill(0, $this->combinations_total, str_repeat(chr(0), $this->input_len));
for(
$group = 0,                                         //Index for the current group of letters.
$groups_count = $this->input_len,                   //Total number of letter groups.
$letters = count(phone::$letters[$this->input[0]]), //Total number of letters in the current group.
$width = $this->combinations_total,                         //Number of bytes to repeat the current letter.
$repeat = 1;                                        //Total number of times the group will repeat.
;
) {
for($byte = 0, $width /= $letters, $r = 0; $r < $repeat; ++$r)
for($l = 0; $l < $letters; ++$l)
for($w = 0; $w < $width; ++$w)
$combinations[$byte++][$group] = phone::$letters[$this->input[$group]][$l];
if(++$group < $groups_count) {
$repeat *= $letters;
$letters = count(phone::$letters[$this->input[$group]]);
}
else
break;
}
return $combinations;
}
}
//====================
$phone = new phone('23456789');
print_r($phone);
//print_r($phone->combinations());
for($i = 0; $i < $phone->combinations_total; ++$i) {
echo $i, ': ', $phone->combination($i)['bytes'], "\n";
}