Alien Dictionary

+10

Une liste de mots est triée selon un alphabet que vous ne connaissez pas : les 26 lettres minuscules de l’anglais, dans un ordre secret. Les mots se comparent comme d’habitude. La première position où deux mots diffèrent détermine l’ordre et, lorsque l’un des mots est le début de l’autre, le mot le plus court vient en premier.

Renvoyez les lettres qui apparaissent dans les mots, sous la forme d’une seule chaîne dans l’ordre alphabétique. Lorsque plusieurs ordres conviennent, 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 l’ordre le plus petit 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 avant ten place a avant n. Les autres paires donnent t avant a, t avant c et a avant c. Aucune règle ne mentionne e, donc le plus petit ordre commence par lui : e, t, a, c, n.

Entrée: words = ["bat", "tab", "tub", "bus"]
Sortie: "invalid"
Explication: bat avant tab place b avant t, et tub avant bus place t avant b. Les deux ne peuvent pas être vrais, 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.

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

Chaque paire de mots voisins donne au plus une règle, à la première position où ils diffèrent : la lettre x avant la lettre y. Un ordre convenable est un ordre topologique de ces règles. Un cycle, ou un mot placé avant son propre préfixe, rend la liste impossible. Un tas minimal qui place toujours la plus petite lettre disponible donne le plus petit ordre.

Essayez toutes les permutations des lettres

Correcte, mais ne termine pas sur les plus gros tests

Intuition

Teste un arrangement des k lettres distinctes en vérifiant chaque paire de mots voisins. À la première position où les lettres diffèrent, celle du premier mot doit venir plus tôt ; s'il n'y a aucune différence, le premier mot ne doit pas être plus long. Parcours les arrangements dans l'ordre croissant à partir de l'ordre alphabétique, avec la permutation suivante, et le premier qui satisfait la condition est le plus petit ordre qui convient.

k lettres ont k! arrangements : 10 en donnent 3,628,800 et 26 environ 4 × 10^26, et chaque test lit jusqu'à 5 × 10^4 caractères. Quand rien ne convient, la recherche les essaie tous.

Algorithme

Rassemblez les lettres distinctes et triez-les par ordre alphabétique.
Notez le rang de chaque lettre dans l’arrangement actuel.
Vérifiez chaque paire voisine : à la première position où elles 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 au suivant, dans l’ordre croissant.
S’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

Pour une paire de voisins, seule la première différence compte : act avant cat indique que a précède c, et les lettres qui suivent ne sont jamais comparées. Chaque paire donne donc au plus une arête.

L'algorithme de Kahn transforme les arêtes en un ordre : compte les arêtes entrantes de chaque lettre, place une lettre dont le compte est égal à 0, supprime ses arêtes sortantes, puis recommence. Une lettre dans un cycle conserve toujours une arête venant de la lettre qui la précède dans le cycle ; elle n'est donc jamais placée. Si moins de lettres sont placées qu'il n'y en a, la réponse est "invalid".

Garde les lettres prêtes dans un tas min et place la plus petite. Tout ordre possible commence par une lettre prête ; c'est donc la plus petite première lettre possible, et la placer ne fait que supprimer des arêtes, sans bloquer aucune autre lettre. Dans le premier exemple, e et t sont prêtes au départ, et e vient en premier. Une simple file donne un ordre valide, mais pas toujours le plus petit.

Algorithme

Marque chaque lettre qui apparaît dans les mots.
Pour chaque paire de mots voisins, trouvez la première position où ils diffèrent et ajoutez une seule fois l’arête entre leurs deux lettres. S’il n’y a aucune différence et que le premier mot est plus long, renvoyez "invalid".
Comptez les arêtes entrantes et placez dans un tas min les lettres marquées dont le compte est égal à 0.
Retirez la plus petite lettre et ajoutez-la. Diminuez le compte de chaque lettre vers laquelle elle pointe, et ajoutez celles dont le compte atteint 0.
Renvoyez les lettres placées si toutes les lettres marquées ont été placées, sinon "invalid".

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

Prendre plusieurs règles dans une même paire. Lire la deuxième position de act et cat ajoute c avant a, et le premier exemple devient un cycle erroné.
Oublier le piège du préfixe. cooking avant cook ne présente aucune lettre différente ; une boucle qui ne gère que les différences renvoie donc un ordre.
Omettre les lettres qui n’apparaissent dans aucune règle. Dans le premier exemple, aucune règle ne mentionne e, alors qu’elle doit figurer dans la réponse.
Compter deux fois une règle répétée dans le degré entrant, mais ne la stocker qu’une fois. La lettre n’atteint jamais 0 et une liste valide est signalée comme un cycle.
Considérer deux mots voisins identiques comme un piège du préfixe ; un mot répété est dans le bon ordre.

Questions fréquentes3

Quelle est la complexité temporelle d’Alien Dictionary ?

O(C + k²), où C est le nombre total de caractères et k ≤ 26 est le nombre de lettres distinctes. Un seul parcours de la liste trouve chaque première différence, et l’algorithme de Kahn parcourt au plus k² arêtes. La table des arêtes utilise un espace O(k²).

Pourquoi comparer uniquement les mots voisins ?

Le fait d’être trié est transitif : 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.

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

Dans chaque alphabet, un mot vient après son propre préfixe, car la comparaison arrive à la fin des lettres du mot le plus court avant de trouver une différence. C’est la seule façon pour qu’une liste soit impossible sans qu’il y ait de cycle entre ses règles.

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

Test #1

Test #2

Test #3

Argument

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

Résultat attendu

"etacn"