Alien Dictionary

+10

Una lista de palabras está ordenada según un alfabeto que no conoces: las 26 letras minúsculas del inglés en cierto orden secreto. Las palabras se comparan de la manera habitual. La primera posición en la que dos palabras difieren determina cuál de las dos letras aparece primero en el alfabeto; y cuando una palabra es el comienzo de la otra, la palabra más corta aparece primero.

Devuelve las letras que aparecen en las palabras, como una sola cadena en orden alfabético. Si varios órdenes son compatibles con la lista, devuelve el que aparece primero en el orden lexicográfico habitual. Si ningún orden es compatible, devuelve "invalid".

Función

alienOrder(words: string-array) → string

wordsstring-array: las palabras, ordenadas según el alfabeto desconocido
Devuelvestring: las letras en el orden más pequeño que encaje, o «invalid»

Restricciones

1 ≤ words.length ≤ 5000
1 ≤ words[i].length ≤ 10
Cada palabra contiene únicamente letras minúsculas del inglés.
La misma palabra puede aparecer más de una vez.

Ejemplos

Entrada: words = ["tea", "ten", "ate", "act", "cat"]
Salida: "etacn"
Explicación: tea y ten difieren por primera vez en a y n, así que a va antes que n. Los otros pares indican que t va antes que a, t antes que c y a antes que c. Ninguna regla menciona e, así que el orden más pequeño la pone primero, después t, después a y luego c y n, que para entonces están libres, con c primero.

Entrada: words = ["bat", "tab", "tub", "bus"]
Salida: "invalid"
Explicación: bat antes de tab coloca b antes de t, tab antes de tub coloca a antes de u y tub antes de bus coloca t antes de b. b antes de t y t antes de b no pueden cumplirse a la vez, así que ningún orden encaja.

Entrada: words = ["cooking", "cook"]
Salida: "invalid"
Explicación: cook es el comienzo de cooking, así que va primero en todos los alfabetos. La lista lo coloca en segundo lugar, algo que ningún orden de las letras puede explicar.

+20 pruebas ocultas al enviar

Para ir más allá

¿Cómo determinarías si el orden de ajuste es el único?

Pistas

Ábrelas de una en una. Cada una revela un poco más.

0 de 3 abiertas

Solución

La lista oculta su alfabeto en los lugares donde las palabras vecinas difieren por primera vez. Cada uno de esos lugares da una regla: la letra x antes que la letra y, y las reglas forman un grafo dirigido sobre las letras. Un orden válido es un orden topológico de ese grafo. Dos cosas hacen que la lista sea imposible: un ciclo entre las reglas y una palabra colocada antes que su propio prefijo. Colocar la letra disponible más pequeña en cada paso, con un montículo mínimo, da el menor orden válido.

Prueba cada orden de las letras

Correcto, pero no termina con las pruebas más grandes

Intuición

La respuesta es algún ordenamiento de las k letras distintas. Puedes probar directamente un ordenamiento: la lista se ajusta a él cuando cada par de palabras vecinas está en orden según ese ordenamiento. Compara las dos palabras en la primera posición en la que difieren; la letra de la primera palabra debe aparecer antes en el ordenamiento. Si nunca difieren, la primera palabra no debe ser más larga. Basta con comprobar las palabras vecinas, porque estar ordenada es una cadena: si cada palabra es menor o igual que la siguiente, toda la lista está ordenada.

Ahora recorre los ordenamientos de menor a mayor. Empieza con las letras en orden alfabético, que es el menor ordenamiento de todos, y avanza cada vez al siguiente mayor (la siguiente permutación). El primer ordenamiento que supera la prueba es el orden más pequeño que encaja. Si ninguno la supera, devuelve "invalid".

Esto es correcto, pero impracticable con datos reales. k letras tienen k! ordenamientos: 5 letras dan 120, 10 dan 3,628,800 y las 26 dan aproximadamente 4 × 10^26. Cada prueba lee toda la lista, C caracteres en total y hasta 5 × 10^4. En las pruebas grandes, el ordenamiento más pequeño que encaja empieza con f o z, así que antes de llegar a él hay que recorrer una cantidad astronómica de ordenamientos; y cuando ninguno encaja, la búsqueda tiene que probarlos todos.

Algoritmo

Recopila las letras distintas y ordénalas alfabéticamente.
Anota la posición de cada letra (su rango) en la disposición actual.
Comprueba cada par de palabras vecinas: en la primera posición diferente, la letra de la primera palabra debe tener un rango menor; si no hay ninguna posición diferente, la primera palabra no debe ser más larga.
Si todos los pares cumplen la condición, devuelve la disposición. De lo contrario, pasa a la siguiente disposición mayor.
Cuando no haya una disposición siguiente, devuelve "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"

Algoritmo de Kahn con un montículo mínimo

Intuición

Lee las reglas a partir de la lista en lugar de adivinar el orden. Toma dos palabras vecinas y encuentra la primera posición en la que difieren. tea y ten coinciden en t y e y difieren en a y n, así que a va antes que n. Ese es todo el mensaje del par. Las letras después de la primera diferencia no dicen nada: act va antes que cat porque a va antes que c, y la c y la t que siguen en act nunca se comparan con la a y la t de cat. Así que cada par da como máximo una regla, una arista de una letra a otra.

Un par sin posiciones diferentes es la trampa del prefijo. Una palabra es el comienzo de la otra, y la más corta debe ir primero en cualquier alfabeto. Que cook vaya antes que cooking está bien y no da ninguna regla. Que cooking vaya antes que cook nunca puede ordenarse, así que devuelve "invalid" de inmediato. Un bucle que solo busca letras diferentes no encuentra nada en este par y sigue hasta devolver un orden para una lista que ningún alfabeto puede producir.

Ahora necesitas un orden de las letras que respete todas las aristas, un ordenamiento topológico. El algoritmo de Kahn construye uno. Cuenta las aristas que apuntan a cada letra (su grado de entrada), coloca una letra cuyo recuento sea 0, elimina sus aristas salientes y repite. Una letra en un ciclo siempre conserva una arista desde la letra anterior del ciclo, así que su recuento nunca llega a 0 y nunca se coloca. Si se colocan menos letras de las que aparecen en las palabras, hay un ciclo y la respuesta es "invalid".

Para obtener el orden más pequeño, mantén las letras cuyo recuento es 0 en un montículo mínimo y coloca siempre la más pequeña. Esta elección voraz es segura. La primera letra de cualquier orden válido tiene grado de entrada 0, así que la letra más pequeña disponible es la primera letra posible más pequeña. Al colocarla, eliminas aristas y nunca bloqueas otra letra: todas las letras que estaban disponibles siguen estándolo. El mismo razonamiento se aplica entonces a la segunda posición, y así sucesivamente. En el primer ejemplo, e y t están disponibles al principio, y e va primero. Una cola normal también daría un orden válido, pero no siempre el más pequeño.

El costo es una pasada por la lista, con C caracteres en total, para encontrar las primeras diferencias. Con k ≤ 26 letras, hay como máximo k² aristas, almacenadas en una tabla de k por k para guardar una regla repetida una sola vez, y el montículo nunca contiene más de k letras. Eso es O(C + k²) de tiempo, unos pocos milisegundos en las pruebas más grandes.

Algoritmo

Marca cada letra que aparece en las palabras.
Para cada par de palabras vecinas, encuentra la primera posición en la que difieren. Si existe, añade una vez la arista desde la letra de la primera palabra hasta la letra de la segunda. Si no existe y la primera palabra es más larga, devuelve "invalid".
Cuenta las aristas entrantes de cada letra y añade a un min-heap cada letra que aparece y cuyo recuento sea 0.
Extrae la letra más pequeña y añádela. Reduce el recuento de cada letra a la que apunta y añade cualquiera cuyo recuento llegue a 0.
Si se colocaron menos letras de las que aparecen, devuelve "invalid". De lo contrario, devuelve las letras colocadas.

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)

Errores comunes y casos límite

La mayoría de las respuestas incorrectas aquí son silenciosas: una regla mal interpretada sigue produciendo algún orden, solo que el incorrecto.

Tomar más de una regla de un par. Solo cuenta la primera posición diferente. act antes de cat indica que a va antes que c y nada sobre las letras que vienen después.
No detectar la trampa del prefijo. cooking antes de cook no tiene ninguna letra diferente, así que un bucle que solo maneja diferencias no detecta nada y devuelve un orden. La respuesta es "invalid".
Omitir letras que no aparecen en ninguna regla. En el primer ejemplo ninguna regla menciona e, pero debe incluirse en la respuesta, y el orden más pequeño la coloca primero.
Usar una cola simple en lugar de un montículo mínimo. El algoritmo de Kahn con una cola devuelve un orden válido, pero el contrato exige el más pequeño.
Contar una regla repetida dos veces en el grado de entrada, pero almacenarla una sola vez en el grafo. Entonces la letra nunca llega a 0 y se informa que una lista válida es un ciclo. Almacena cada regla una sola vez, o añádela y elimínala la misma cantidad de veces.
Tratar dos palabras iguales consecutivas como la trampa del prefijo. Una palabra seguida de la misma palabra está en orden; solo es imposible que una palabra más larga aparezca antes que su propio prefijo.

Preguntas frecuentes4

¿Cuál es la complejidad temporal de Alien Dictionary?

O(C + k²), donde C es el número total de caracteres de las palabras y k ≤ 26 es el número de letras distintas. Una pasada por la lista encuentra la primera diferencia de cada par de palabras vecinas, y el algoritmo de Kahn visita como máximo k² aristas. El min-heap añade O(k log k), que es poco en comparación con el resto. La tabla de aristas ocupa un espacio de O(k²).

¿Por qué comparar solo las palabras vecinas?

Estar ordenada es una propiedad transitiva: si cada palabra es menor o igual que la siguiente, toda la lista está ordenada. Así que cualquier regla que puedas deducir de dos palabras distantes ya se cumple en los pares vecinos que hay entre ellas. Comparar cada par de palabras no aporta información y cuesta O(n²) comparaciones en lugar de n-1.

¿Por qué elegir la letra disponible más pequeña da el orden más pequeño?

Cualquier orden válido debe empezar con una letra a la que no apunte ninguna regla. Por lo tanto, la letra más pequeña de estas es la primera letra posible más pequeña, y colocarla solo elimina aristas, así que todas las demás letras disponibles siguen estando disponibles. Al repetir el argumento en cada posición, se construye el orden más pequeño letra por letra. Un montículo mínimo te proporciona la letra disponible más pequeña en O(log k).

¿Por qué una palabra delante de su propio prefijo no es válida?

En todo alfabeto, una palabra va después de su propio prefijo, porque la comparación se queda sin letras en la palabra más corta antes de encontrar una diferencia. Así que cooking antes de cook está fuera de orden, sean cuales sean las letras, y ninguna regla puede corregirlo. Es la única manera en que una lista puede ser imposible sin que haya ningún ciclo entre sus reglas.

Python

def alienOrder(words):
    # Escribe el código aquí

Casos de prueba

Caso 1

Caso 2

Caso 3

Entrada

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

Esperado

"etacn"