Letter Combinations of a Phone Number

Q: Quelle est la complexité temporelle de la combinaison de lettres d’un numéro de téléphone ?

O(4^n · n) pour n chiffres : il peut y avoir 4^n chaînes, lorsque chaque chiffre est 7 ou 9, et chacune nécessite n étapes pour être écrite. C'est la taille de la sortie, donc aucune solution ne fait mieux. Le retour arrière nécessite un espace supplémentaire de O(n) , en plus de la sortie.

MoyenRetour sur trace

+10

Sur un clavier téléphonique, chaque chiffre de 2 à 9 correspond à quelques lettres : 2 correspond à abc, 3 à def, 4 à ghi, 5 à jkl, 6 à mno, 7 à pqrs, 8 à tuv et 9 à wxyz.

Tu reçois une chaîne de caractères digits. Choisis une lettre pour chaque chiffre, en conservant l’ordre des chiffres, et tu obtiens une chaîne que les touches peuvent saisir. Renvoie toutes ces chaînes, triées par ordre lexicographique (ordre du dictionnaire).

Fonction

letterCombinations(digits: string) → string-array

digitsstring: les chiffres saisis, chacun compris entre 2 et 9
Renvoiestring-array: chaque chaîne que les touches peuvent saisir, par ordre lexicographique

Contraintes

1 ≤ digits.length ≤ 4
Chaque caractère de digits est un chiffre compris entre 2 et 9.
La réponse contient au maximum 4⁴ = 256 chaînes.

Exemples

Entrée: digits = "23"
Sortie: ["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"]
Explication: 2 propose a, b, c et 3 propose d, e, f. Chaque première lettre est associée à chaque deuxième lettre : 3 × 3 = 9 chaînes, triées de sorte que la première lettre change le plus lentement.

Entrée: digits = "94"
Sortie: ["wg", "wh", "wi", "xg", "xh", "xi", "yg", "yh", "yi", "zg", "zh", "zi"]
Explication: 9 s’écrit avec quatre lettres et 4 avec trois, donc il y a 4 × 3 = 12 chaînes. Les trois chaînes qui commencent par w précèdent la première qui commence par x.

Pour aller plus loin

Supposons que tu ne veuilles que les combinaisons qui sont de vrais mots du dictionnaire. Comment éviterais-tu de construire d’abord toutes les chaînes de longueur 4^n ?

Indices

Ouvrez-les un par un. Chacun en dévoile un peu plus.

0 sur 3 ouverts

Solution

La réponse contient jusqu’à 4^n chaînes, donc chaque solution demande au moins autant de travail pour les écrire. Ce qui compte, c’est de produire chaque choix une seule fois, sans en omettre ni en répéter. C’est du retour sur trace dans un arbre de décision avec un niveau par chiffre, où chaque feuille est une réponse.

Construis les chaînes chiffre par chiffre

Intuition

Commence avec une liste contenant une chaîne vide et étends-la un chiffre à la fois. Pour "23", le chiffre 2 la transforme en a, b, c, et le 3 développe chacune de ces chaînes avec d, e et f, ce qui donne neuf chaînes.

L’ordre reste trié. Si la liste est triée avant un chiffre, tu étends les préfixes dans cet ordre, et chaque préfixe avec les lettres de sa touche de gauche à droite : un préfixe précédent reste en premier, et les préfixes identiques sont ordonnés selon la nouvelle lettre.

Le travail est proportionnel à la taille de la réponse, mais pendant que tu construis un niveau, tout le niveau précédent reste aussi en mémoire.

Algorithme

Commencez avec combos = [""], un préfixe vide.
Pour chaque chiffre, créez une nouvelle liste : pour chaque préfixe dans combos et chaque lettre sur la touche de ce chiffre, ajoutez prefix + letter.
Remplacez combos par la nouvelle liste.
Après le dernier chiffre, renvoyez combos.

KEYPAD = {"2": "abc", "3": "def", "4": "ghi", "5": "jkl",
          "6": "mno", "7": "pqrs", "8": "tuv", "9": "wxyz"}


def letterCombinations(digits):
    combos = [""]  # every prefix built so far; one empty prefix to start
    for digit in digits:
        # Each old prefix grows by each letter of this digit, in order.
        combos = [prefix + letter for prefix in combos for letter in KEYPAD[digit]]
    return combos

Retour arrière dans l’arbre de décision

Intuition

Les réponses sont les feuilles d’un arbre de décision. La racine est la chaîne vide, et chaque niveau ajoute une lettre du chiffre suivant : pour "23", la racine a pour enfants a, b, c, chacun ayant pour enfants d, e, f.

Parcourez-le en profondeur avec un seul tampon, path. Au niveau i, choisissez une lettre de digits[i] en l’ajoutant, explorez en appelant récursivement la fonction avec i+1, puis annulez en la supprimant. Cette annulation permet à un seul tampon de servir pour tout l’arbre : après ad, ae et af, retirer la dernière lettre ramène path à a, puis à la chaîne vide, prêt pour b. Lorsque i atteint la fin de digits, enregistrez une copie.

La complexité temporelle reste O(4^n · n), mais la mémoire supplémentaire se limite au tampon et à la pile d’appels, soit O(n).

Algorithme

Gardez un path vide et un result vide.
Définissez backtrack(i) : si i est égal à la longueur de digits, enregistrez une copie de path et retournez.
Sinon, pour chaque lettre sur la touche correspondant à digits[i], dans l’ordre : ajoutez-la à path, appelez backtrack(i+1), puis retirez-la.
Appelez backtrack(0) et retournez result.

KEYPAD = {"2": "abc", "3": "def", "4": "ghi", "5": "jkl",
          "6": "mno", "7": "pqrs", "8": "tuv", "9": "wxyz"}


def letterCombinations(digits):
    result = []
    path = []  # the letters chosen so far, one per digit

    def backtrack(i):
        if i == len(digits):
            # Every digit has a letter: this leaf is one finished string.
            result.append("".join(path))
            return
        for letter in KEYPAD[digits[i]]:
            path.append(letter)   # choose
            backtrack(i + 1)      # explore the digits after this one
            path.pop()            # undo, so the next letter can take its place

    backtrack(0)
    return result

Pièges et cas limites

En supposant que chaque touche comporte trois lettres. Prendre trois lettres à partir de l’index (d-2)*3 de l’alphabet omet le s du 7 et commence le 8 par s. Écris le clavier sous forme de tableau.
Oublier l’annulation. path continue de grandir, et la deuxième réponse pour "23" donne ade au lieu de ae.
Enregistrer le tampon au lieu d’une copie. En Python, result.append(path) stocke neuf fois la même liste, et à la fin, elle est vide.
Essayer les lettres d’une touche de droite à gauche, ou construire les chaînes à partir d’une pile dans la version itérative. Dans les deux cas, l’ordre trié est rompu.
En PHP et en R, "23" peut être reçu comme le nombre 23. Convertis-le en texte avant d’indexer ses caractères.

Questions fréquentes3

Quelle est la complexité temporelle de la combinaison de lettres d’un numéro de téléphone ?

O(4^n · n) pour n chiffres : il peut y avoir 4^n chaînes, lorsque chaque chiffre est 7 ou 9, et chacune nécessite n étapes pour être écrite. C'est la taille de la sortie, donc aucune solution ne fait mieux. Le retour arrière nécessite un espace supplémentaire de O(n), en plus de la sortie.

Pourquoi le retour sur trace renvoie-t-il les combinaisons dans l’ordre trié ?

Toutes les réponses ont la même longueur, et un parcours en profondeur termine toutes les chaînes qui commencent par a avant de choisir b. Il en va de même à chaque niveau, tant que les lettres de chaque clé sont essayées de gauche à droite. C’est l’ordre du dictionnaire, donc aucun tri n’est nécessaire.

Et les chiffres 0 et 1 ?

Sur un pavé numérique de téléphone, 0 et 1 ne correspondent à aucune lettre, et cette version n’utilise que les chiffres de 2 à 9. S’ils pouvaient apparaître, il faudrait décider si un tel chiffre est ignoré ou s’il rend la réponse vide. Lors d’un entretien, demande quelle option est souhaitée.

def letterCombinations(digits):
    # Écrivez le code ici

Test #1

Test #2

Test #3

Argument

digits = "23"

Résultat attendu

["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"]