Letter Combinations of a Phone Number

Q: Quelle est la complexité temporelle de la génération des combinaisons de lettres d’un numéro de téléphone ?

C’est 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. Avec des touches de trois lettres seulement, c’est O(3^n · n) . Aucune solution ne peut faire mieux, car c’est la taille de la sortie. Le retour sur trace nécessite O(n) espace supplémentaire, en plus de la sortie.

MoyenRetour sur trace

+10

Sur le clavier d’un téléphone, 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.

Vous recevez une chaîne digits. Choisissez une lettre pour chaque chiffre, en gardant les chiffres dans leur ordre, et vous obtenez une chaîne que les touches peuvent saisir. Renvoyez toutes ces chaînes, triées dans l’ordre lexicographique (alphabétique). Pour "23", il y a neuf chaînes, de "ad" à "cf".

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, dans l’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, donc il y a 3 × 3 = 9 chaînes, et les énumérer en faisant varier la première lettre le plus lentement permet de les garder triées.

Entrée: digits = "94"
Sortie: ["wg", "wh", "wi", "xg", "xh", "xi", "yg", "yh", "yi", "zg", "zh", "zi"]
Explication: 9 a quatre lettres et 4 en a 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.

+14 tests cachés à la soumission

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 4^n caractères ?

Indices

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

0 sur 3 ouverts

Solution

Rien ici ne peut être omis : la réponse elle-même peut contenir jusqu’à 4^n chaînes, donc toute solution correcte consacre au moins autant de travail à les écrire. Ce que le problème teste, c’est si tu peux générer un ensemble de choix de manière systématique, sans en oublier ni en répéter un. C’est du retour sur trace dans sa forme la plus simple : un arbre de décision avec un niveau par chiffre, parcouru en profondeur d’abord, où chaque feuille est une réponse.

Construisez les chaînes chiffre par chiffre

Intuition

Construis les réponses un chiffre à la fois. Commence par une liste qui contient une chaîne vide. Pour "23", le chiffre 2 la transforme en a, b, c. Le chiffre 3 ajoute ensuite d, e et f à chacune de ces trois chaînes, ce qui donne neuf chaînes de longueur 2. Après le dernier chiffre, la liste contient toutes les réponses.

L’ordre est trié sans effort supplémentaire. Supposons que la liste soit triée avant un chiffre. Tu prolonges les préfixes dans ce même ordre, et chaque préfixe avec les lettres de la touche de gauche à droite. Une chaîne dont le préfixe apparaît plus tôt vient toujours en premier, et deux chaînes ayant le même préfixe sont ordonnées selon la nouvelle lettre, comme dans l’ordre du dictionnaire.

Le coût dépend de la taille de la réponse. Avec n chiffres, la dernière liste contient jusqu’à 4^n chaînes de longueur n, et toutes les listes précédentes réunies contiennent au plus moitié moins de chaînes, toutes plus courtes. L’inconvénient est la mémoire : pendant que tu construis un niveau, tout le niveau précédent est également conservé, y compris chaque court préfixe dont tu vas te débarrasser.

Algorithme

Commencez avec combos = [""], un préfixe vide.
Pour chaque chiffre, créez une nouvelle liste : pour chaque préfixe de 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

Considérez la réponse comme un arbre de décision. La racine est une chaîne vide. Pour "23", elle a trois enfants, a, b et c, un pour chaque lettre de 2. Chacun de ces enfants en a trois à son tour, un pour chaque lettre de 3. L’arbre a un niveau par chiffre, et les neuf feuilles, de ad à cf, sont exactement les réponses.

Le retour sur trace parcourt cet arbre en profondeur à l’aide d’un seul tampon, path. Au niveau i, vous choisissez une lettre de digits[i] en l’ajoutant, vous explorez tout ce qui se trouve en dessous en appelant récursivement la fonction avec i+1, puis vous annulez le choix en retirant la lettre. C’est cette annulation qui permet à un seul tampon de servir pour tout l’arbre : après avoir enregistré ad, ae et af, le retrait ramène path à a, puis à la chaîne vide, prêt pour b. Lorsque i est égal à la longueur de digits, le tampon constitue une réponse complète, et vous en enregistrez une copie.

Essayer les lettres de gauche à droite à chaque niveau permet de parcourir les feuilles dans l’ordre lexicographique ; le résultat n’a donc pas besoin d’être trié. Dans ce problème, chaque branche aboutit à une réponse : il n’y a donc rien à élaguer ; l’arbre ne fait que 4 niveaux de profondeur et compte au maximum 256 feuilles. Le travail reste en O(4^n · n) pour écrire les réponses, mais la mémoire supplémentaire se limite au tampon et à la pile d’appels, soit O(n), au lieu de stocker tout un niveau de préfixes. La même boucle choisir, explorer, annuler permet de résoudre les problèmes de sous-ensembles, de permutations, de somme de combinaisons et de recherche de mots.

Algorithme

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

La recherche en elle-même est courte ; la plupart des bogues viennent donc du clavier ou du tampon partagé.

Supposer que chaque touche a trois lettres. 7 correspond à pqrs et 9 à wxyz ; prendre trois lettres à partir de l’index (d-2)*3 de l’alphabet omet donc le s de 7 et fait commencer 8 par s au lieu de t. Écrivez le clavier sous forme de tableau.
Oublier l’annulation. Sans retirer la lettre après l’appel récursif, path continue de s’allonger, et la deuxième réponse pour "23" devient ade au lieu de ae.
Enregistrer le tampon au lieu d’une copie. En Python, result.append(path) enregistre neuf fois la même liste, qui est vide à la fin. Convertissez-la en une nouvelle chaîne au moment de l’enregistrer.
Perdre l’ordre. Essayer les lettres d’une touche de droite à gauche, ou construire les chaînes à partir d’une pile dans la version itérative, donne les réponses dans un ordre différent de l’ordre trié demandé par le problème.
Lire une chaîne de chiffres comme un nombre. Dans les langages à typage faible comme PHP et R, "23" peut vous parvenir sous la forme du nombre 23. Convertissez-le en texte avant d’accéder à ses caractères par index.

Questions fréquentes4

Quelle est la complexité temporelle de la génération des combinaisons de lettres d’un numéro de téléphone ?

C’est 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. Avec des touches de trois lettres seulement, c’est O(3^n · n). Aucune solution ne peut faire mieux, car c’est la taille de la sortie. Le retour sur trace nécessite O(n) espace supplémentaire, en plus de la sortie.

Peux-tu résoudre Letter Combinations sans récursion ?

Oui. Construis les réponses niveau par niveau : commence par une chaîne vide et, pour chaque chiffre, complète chaque chaîne obtenue avec chaque lettre de cette touche. Cela demande la même quantité de travail et parcourt le même arbre en largeur plutôt qu’en profondeur. Cette méthode garde en mémoire tout un niveau de préfixes, tandis que la récursion n’a besoin que d’une pile aussi profonde que le nombre de chiffres.

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

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

Et les chiffres 0 et 1 ?

Sur un clavier de téléphone, 0 et 1 ne correspondent à aucune lettre, et cette version du problème 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, puisqu’il ne propose aucune lettre à choisir. Lors d’un entretien, demande quelle option est souhaitée avant de coder la solution.

Python

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

Cas de test

Cas 1

Cas 2

Cas 3

Entrée

digits = "23"

Attendu

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