Alien Dictionary

+10

Une liste de mots est triée selon un alphabet que vous ne connaissez pas : les 26 lettres minuscules anglaises dans un ordre secret. Les mots se comparent de la manière habituelle. La première position où deux mots diffèrent détermine lequel vient en premier dans l’alphabet, selon l’ordre de leurs deux lettres à cette position ; si un mot est le début d’un autre, le mot le plus court vient en premier.

Renvoyez les lettres qui apparaissent dans les mots, sous la forme d’une chaîne unique dans l’ordre de l’alphabet. Lorsque plusieurs ordres conviennent à la liste, renvoyez celui qui vient en premier dans l’ordre lexicographique habituel. Lorsqu’aucun ordre ne convient, renvoyez "invalid".

Fonction

alienOrder(words: string-array) → string

wordsstring-array: les mots, triés dans l’alphabet inconnu
Renvoiestring: les lettres dans le plus petit ordre qui convient, ou "invalid"

Contraintes

1 ≤ words.length ≤ 5000
1 ≤ words[i].length ≤ 10
Chaque mot ne contient que des lettres minuscules de l’alphabet anglais.
Le même mot peut apparaître plusieurs fois.

Exemples

Entrée: words = ["tea", "ten", "ate", "act", "cat"]
Sortie: "etacn"
Explication: tea et ten diffèrent d’abord à a et n, donc a vient avant n. Les autres paires indiquent que t vient avant a, t avant c et a avant c. Aucune règle ne mentionne e, donc l’ordre le plus petit le place en premier, puis t, puis a, puis c et n, qui sont tous deux libres à ce moment-là, avec c en premier.

Entrée: words = ["bat", "tab", "tub", "bus"]
Sortie: "invalid"
Explication: bat avant tab place b avant t, tab avant tub place a avant u, et tub avant bus place t avant b. b avant t et t avant b ne peuvent pas être vrais en même temps, donc aucun ordre ne convient.

Entrée: words = ["cooking", "cook"]
Sortie: "invalid"
Explication: cook est le début de cooking, donc il vient en premier dans tous les alphabets. La liste le place en deuxième position, ce qu’aucun ordre des lettres ne peut expliquer.

+20 tests cachés à la soumission

Pour aller plus loin

Comment déterminer si l’ordre d’ajustement est le seul possible ?

Indices

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

0 sur 3 ouverts

Solution

La liste dissimule son alphabet aux endroits où deux mots voisins diffèrent pour la première fois. Chacun de ces endroits donne une règle, la lettre x avant la lettre y, et les règles forment un graphe orienté sur les lettres. Un ordre compatible est un ordre topologique de ce graphe. Deux choses rendent la liste impossible : un cycle parmi les règles, et un mot placé avant son propre préfixe. Placer la plus petite lettre disponible à chaque étape, à l’aide d’un tas min, donne le plus petit ordre compatible.

Essayez chaque ordre possible des lettres

Correcte, mais ne termine pas sur les plus gros tests

Intuition

La réponse est un arrangement des k lettres distinctes. Tu peux tester directement un arrangement : la liste lui correspond si chaque paire de mots voisins est dans l’ordre selon cet arrangement. Compare les deux mots à la première position où ils diffèrent ; la lettre du premier mot doit venir avant dans l’arrangement. S’ils ne diffèrent jamais, le premier mot ne doit pas être plus long. Il suffit de vérifier les mots voisins, car le tri forme une chaîne : si chaque mot est inférieur ou égal au suivant, la liste entière est triée.

Parcours maintenant les arrangements du plus petit au plus grand. Commence par les lettres dans l’ordre alphabétique, qui est le plus petit arrangement de tous, puis passe chaque fois au suivant, plus grand (la permutation suivante). Le premier arrangement qui réussit le test est l’ordre le plus petit qui convient. Si aucun ne convient, renvoie "invalid".

C’est correct, mais impraticable avec de vraies entrées. k lettres ont k! arrangements : 5 lettres en donnent 120, 10 en donnent 3,628,800 et les 26 en donnent environ 4 × 10^26. Chaque test parcourt toute la liste, soit C caractères au total, jusqu’à 5 × 10^4. Dans les grands tests, le plus petit ordre qui convient commence par f ou z : un nombre astronomique d’arrangements le précède, et quand aucun ne convient, la recherche doit tous les essayer.

Algorithme

Rassemblez les lettres distinctes et triez-les par ordre alphabétique.
Notez la position de chaque lettre (son rang) dans l’arrangement actuel.
Vérifiez chaque paire de mots voisins : à la première position où les lettres diffèrent, la lettre du premier mot doit avoir le rang le plus petit ; s’il n’y a aucune différence, le premier mot ne doit pas être plus long.
Si toutes les paires sont valides, renvoyez l’arrangement. Sinon, passez à l’arrangement suivant, dans l’ordre croissant.
Lorsqu’il n’y a pas d’arrangement suivant, renvoyez "invalid".

from itertools import permutations


def fits(words, rank):
    # The list is sorted under rank when every neighbouring pair is in order.
    for first, second in zip(words, words[1:]):
        for x, y in zip(first, second):
            if x != y:
                if rank[x] > rank[y]:
                    return False
                break
        else:
            # One word starts the other: the shorter must come first.
            if len(first) > len(second):
                return False
    return True


def alienOrder(words):
    letters = sorted(set("".join(words)))
    # permutations() of a sorted list yields the orders from smallest to largest,
    # so the first order that fits is the answer.
    for order in permutations(letters):
        rank = {ch: i for i, ch in enumerate(order)}
        if fits(words, rank):
            return "".join(order)
    return "invalid"

Algorithme de Kahn avec un tas min

Intuition

Lisez les règles dans la liste au lieu de deviner l’ordre. Prenez deux mots voisins et trouvez la première position où ils diffèrent. tea et ten ont les mêmes lettres t et e et diffèrent ensuite par a et n, donc a vient avant n. C’est tout ce que cette paire nous apprend. Les lettres qui suivent la première différence ne nous apprennent rien : act vient avant cat parce que a vient avant c, et les lettres c et t qui suivent dans act ne sont jamais comparées aux lettres a et t de cat. Chaque paire donne donc au plus une règle, une arête d’une lettre à une autre.

Une paire sans position différente est un piège de préfixe. Un mot est le début de l’autre, et le plus court doit venir en premier dans tout alphabet. cook avant cooking convient et ne donne aucune règle. cooking avant cook ne peut jamais être trié, donc renvoyez immédiatement "invalid". Une boucle qui ne cherche que les lettres différentes ne trouve rien dans cette paire et continue jusqu’à renvoyer un ordre pour une liste qu’aucun alphabet ne peut produire.

Il vous faut maintenant un ordre des lettres qui respecte toutes les arêtes, un ordre topologique. L’algorithme de Kahn en construit un. Comptez les arêtes qui pointent vers chaque lettre (son degré entrant), placez une lettre dont le compte est 0, supprimez ses arêtes sortantes et recommencez. Une lettre faisant partie d’un cycle conserve toujours une arête provenant de la lettre qui la précède dans le cycle : son compte n’atteint donc jamais 0 et elle n’est jamais placée. Si moins de lettres sont placées qu’il n’y en a dans les mots, il y a un cycle et la réponse est "invalid".

Pour obtenir le plus petit ordre, gardez les lettres dont le compte est 0 dans un tas min et placez toujours la plus petite. Ce choix glouton est sûr. La première lettre de tout ordre qui convient a un compte de 0, donc la plus petite lettre disponible est la plus petite première lettre possible. La placer supprime des arêtes et ne bloque jamais une autre lettre : toute lettre qui était disponible le reste. Le même raisonnement s’applique ensuite à la deuxième position, et ainsi de suite. Dans le premier exemple, e et t sont toutes deux disponibles au départ, et e vient en premier. Une simple file donnerait aussi un ordre valide, mais pas toujours le plus petit.

Le coût est un parcours de la liste, qui contient C caractères au total, pour trouver les premières différences. Avec k ≤ 26 lettres, il y a au plus k² arêtes, conservées dans un tableau k par k afin qu’une règle répétée ne soit stockée qu’une seule fois, et le tas ne contient jamais plus de k lettres. Cela représente O(C + k²) en temps, soit quelques millisecondes pour les tests les plus volumineux.

Algorithme

Marquez chaque lettre qui apparaît dans les mots.
Pour chaque paire de mots voisins, trouvez la première position où ils diffèrent. S’il y en a une, ajoutez une fois l’arête de la lettre du premier mot vers celle du second. S’il n’y en a pas et que le premier mot est plus long, renvoyez "invalid".
Comptez les arêtes entrantes de chaque lettre et placez dans un tas min les lettres présentes dont le nombre est égal à 0.
Retirez la plus petite lettre et ajoutez-la. Diminuez le nombre de chaque lettre vers laquelle elle pointe, et ajoutez celles dont le nombre atteint 0.
Si moins de lettres ont été placées qu’il n’en apparaît, renvoyez "invalid". Sinon, renvoyez les lettres placées.

import heapq


def alienOrder(words):
    # Letters are numbered 0 for 'a' up to 25 for 'z'.
    present = [False] * 26
    for word in words:
        for ch in word:
            present[ord(ch) - 97] = True
    # before[a][b] is True once you know letter a comes before letter b.
    before = [[False] * 26 for _ in range(26)]
    indegree = [0] * 26
    for first, second in zip(words, words[1:]):
        for x, y in zip(first, second):
            if x != y:
                # Only the first difference tells you anything.
                a, b = ord(x) - 97, ord(y) - 97
                if not before[a][b]:
                    before[a][b] = True
                    indegree[b] += 1
                break
        else:
            # No difference: one word starts the other, so the shorter must come first.
            if len(first) > len(second):
                return "invalid"
    # A min-heap of the letters with nothing left before them.
    heap = [c for c in range(26) if present[c] and indegree[c] == 0]
    heapq.heapify(heap)
    order = []
    while heap:
        c = heapq.heappop(heap)
        order.append(chr(c + 97))
        for nxt in range(26):
            if before[c][nxt]:
                indegree[nxt] -= 1
                if indegree[nxt] == 0:
                    heapq.heappush(heap, nxt)
    # A letter on a cycle never gets down to indegree 0, so it is never placed.
    if len(order) < sum(present):
        return "invalid"
    return "".join(order)

Pièges et cas limites

La plupart des mauvaises réponses ici sont silencieuses : une règle mal interprétée produit quand même un ordre, simplement incorrect.

Prendre plusieurs règles dans une paire. Seule la première position où les mots diffèrent compte. act avant cat indique que a précède c, et ne dit rien sur les lettres qui suivent.
Passer à côté du piège du préfixe. cooking avant cook ne comporte aucune lettre différente, donc une boucle qui ne traite que les différences ne voit rien et renvoie un ordre. La réponse est "invalid".
Omettre les lettres qui n’apparaissent dans aucune règle. Dans le premier exemple, aucune règle ne mentionne e, pourtant cette lettre doit figurer dans la réponse, et l’ordre le plus petit la place en premier.
Utiliser une simple file au lieu d’un tas min. L’algorithme de Kahn avec une file renvoie un ordre valide, mais la consigne demande le plus petit.
Compter une règle répétée deux fois dans le degré entrant, mais ne la stocker qu’une fois dans le graphe. La lettre n’atteint alors jamais 0, et une liste valide est signalée à tort comme un cycle. Stocke chaque règle une seule fois, ou ajoute-la et supprime-la le même nombre de fois.
Considérer deux mots identiques adjacents comme un piège du préfixe. Un mot suivi du même mot est dans le bon ordre ; seul un mot plus long placé avant son propre préfixe est impossible.

Questions fréquentes4

Quelle est la complexité temporelle de l’« Alien Dictionary » ?

O(C + k²), où C est le nombre total de caractères dans les mots et k ≤ 26 est le nombre de lettres distinctes. Un seul parcours de la liste permet de trouver la première différence de chaque paire de mots voisins, et l’algorithme de Kahn parcourt au plus k² arêtes. Le tas min ajoute O(k log k), ce qui est négligeable par rapport au reste. La table des arêtes occupe O(k²) espace.

Pourquoi comparer uniquement les mots voisins ?

Le fait d’être triée est une propriété transitive : si chaque mot est inférieur ou égal au suivant, toute la liste est triée. Ainsi, toute règle que l’on pourrait déduire de deux mots éloignés découle déjà des paires voisines qui les séparent. Comparer chaque paire de mots n’apporte aucune information supplémentaire et nécessite O(n²) comparaisons au lieu de n-1.

Pourquoi choisir la plus petite lettre disponible donne-t-il le plus petit ordre ?

Tout ordre valide doit commencer par une lettre vers laquelle aucune règle ne pointe. La plus petite de ces lettres est donc la plus petite première lettre possible, et la placer ne fait que supprimer des arêtes, si bien que toutes les autres lettres disponibles le restent. En répétant le raisonnement à chaque position, on construit le plus petit ordre, lettre par lettre. Un tas min vous donne la plus petite lettre disponible en O(log k).

Pourquoi un mot placé avant son propre préfixe est-il invalide ?

Dans tout alphabet, un mot vient après son propre préfixe, car la comparaison arrive au bout des lettres du mot le plus court avant de trouver une différence. Ainsi, cooking avant cook est dans le désordre, quels que soient les lettres, et aucune règle ne peut corriger cela. C’est la seule façon pour qu’une liste soit impossible sans qu’il y ait de cycle entre ses règles.

Python

def alienOrder(words):
    # Écrivez le code ici

Cas de test

Cas 1

Cas 2

Cas 3

Entrée

words = ["tea", "ten", "ate", "act", "cat"]

Attendu

"etacn"