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 algún orden secreto. Las palabras se comparan como de costumbre. La primera posición en la que dos palabras difieren determina el orden y, cuando una palabra es el inicio de otra, la más corta va primero.

Devuelve las letras que aparecen en las palabras, como una sola cadena ordenada alfabéticamente. Si encajan varios órdenes, devuelve el que aparece primero en el orden habitual del diccionario. Si no encaja ningún orden, 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 antes de ten coloca a antes que n. Los otros pares indican t antes que a, t antes que c y a antes que c. Ninguna regla menciona e, así que el orden más pequeño empieza con ella: e, t, a, c, n.

Entrada: words = ["bat", "tab", "tub", "bus"]
Salida: "invalid"
Explicación: bat antes de tab pone b antes de t, y tub antes de bus pone t antes de b. Ambas cosas no pueden cumplirse, 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 pone en segundo lugar, algo que ningún orden de las letras puede explicar.

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

Cada par de palabras vecinas da como máximo una regla, en la primera posición en la que difieren: la letra x antes de la letra y. Un orden válido es un orden topológico de esas reglas. Un ciclo, o una palabra colocada antes que su propio prefijo, hace que la lista sea imposible. Un montículo mínimo que siempre coloca la letra disponible más pequeña da el orden más pequeño.

Prueba todos los órdenes de las letras

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

Intuición

Prueba una disposición de las k letras distintas comprobando cada par de palabras vecinas. En la primera posición diferente, la letra de la primera palabra debe ir antes; si no hay diferencias, la primera palabra no debe ser más larga. Recorre las disposiciones en orden ascendente desde la alfabética usando la permutación siguiente, y la primera que cumpla las condiciones es el orden más pequeño que encaja.

Las k letras tienen k! disposiciones: 10 dan 3,628,800 y 26 dan aproximadamente 4 × 10^26, y cada prueba lee hasta 5 × 10^4 caracteres. Cuando nada encaja, la búsqueda las prueba todas.

Algoritmo

Recopila las letras distintas y ordénalas alfabéticamente.
Anota el rango de cada letra en la disposición actual.
Comprueba cada par de palabras vecinas: en la primera posición donde difieran, la letra de la primera palabra debe tener un rango menor; si no hay diferencias, 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 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

En un par de vecinos, solo cuenta la primera diferencia: que act vaya antes que cat indica que a va antes que c, y las letras posteriores nunca se comparan. Así que cada par aporta como máximo una arista.

El algoritmo de Kahn convierte las aristas en un orden: cuenta las aristas entrantes de cada letra, coloca una letra cuyo conteo sea 0, elimina sus aristas salientes y repite. Una letra que está en un ciclo siempre conserva una arista desde la letra anterior del ciclo, así que nunca se coloca. Si se colocan menos letras de las que aparecen, la respuesta es "invalid".

Mantén las letras disponibles en un montículo mínimo y coloca la menor. Cualquier orden válido empieza con una letra disponible, así que esta es la letra inicial más pequeña posible, y colocarla solo elimina aristas, por lo que no bloquea ninguna otra letra. En el primer ejemplo, e y t están disponibles al principio, y e va primero. Una cola común da un orden válido, pero no siempre el más pequeño.

Algoritmo

Marca todas las letras que aparecen en las palabras.
Para cada par de palabras vecinas, encuentra la primera posición diferente y añade una arista entre sus dos letras, una sola vez. Si no hay diferencias y la primera palabra es más larga, devuelve "invalid".
Cuenta las aristas entrantes y añade a un montículo mínimo cada letra marcada 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 las que lleguen a 0.
Devuelve las letras ordenadas si se colocaron todas las letras marcadas; de lo contrario, devuelve "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)

Errores comunes y casos límite

Tomar más de una regla de un par. Leer la segunda posición de act y cat añade c antes de a, y el primer ejemplo se convierte en un ciclo falso.
No tener en cuenta la trampa del prefijo. cooking antes de cook no tiene ninguna letra distinta, así que un bucle que solo maneja diferencias devuelve un orden.
Omitir las letras que no aparecen en ninguna regla. En el primer ejemplo ninguna regla menciona la e, pero debe formar parte de la respuesta.
Contar una regla repetida dos veces en el grado de entrada, pero almacenarla una sola vez. La letra nunca llega a 0 y se informa de una lista válida como si fuera un ciclo.
Tratar dos palabras vecinas iguales como una trampa del prefijo; una palabra repetida está en orden.

Preguntas frecuentes3

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

O(C + k²), donde C es el número total de caracteres y k ≤ 26 es el número de letras distintas. Una pasada por la lista encuentra cada primera diferencia, y el algoritmo de Kahn visita como máximo k² aristas. La tabla de aristas ocupa un espacio O(k²).

¿Por qué comparar solo 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 alejadas ya se cumple gracias a los pares vecinos que hay entre ellas.

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

En todos los alfabetos, 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. Es la única forma en que una lista puede ser imposible sin que haya ningún ciclo entre sus reglas.

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

Prueba #1

Prueba #2

Prueba #3

Argumento

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

Salida Esperada

"etacn"