Alien Dictionary

+10

Uma lista de palavras está ordenada segundo um alfabeto que você não conhece: as 26 letras minúsculas do inglês em alguma ordem secreta. As palavras são comparadas normalmente. A primeira posição em que duas palavras diferem determina a ordem e, quando uma palavra é o início da outra, a palavra mais curta vem primeiro.

Retorne as letras que aparecem nas palavras, em uma única string na ordem do alfabeto. Quando várias ordens forem possíveis, retorne a que vem primeiro na ordem alfabética comum. Quando nenhuma ordem for possível, retorne "invalid".

Função

alienOrder(words: string-array) → string

wordsstring-array: as palavras, ordenadas no alfabeto desconhecido
Retornastring: as letras na menor ordem que se encaixa, ou "invalid"

Restrições

1 ≤ words.length ≤ 5000
1 ≤ words[i].length ≤ 10
Cada palavra contém apenas letras minúsculas do alfabeto inglês.
A mesma palavra pode aparecer mais de uma vez.

Exemplos

Entrada: words = ["tea", "ten", "ate", "act", "cat"]
Saída: "etacn"
Explicação: tea antes de ten coloca a antes de n. Os outros pares indicam t antes de a, t antes de c e a antes de c. Nenhuma regra menciona e, então a menor ordem começa com ele: e, t, a, c, n.

Entrada: words = ["bat", "tab", "tub", "bus"]
Saída: "invalid"
Explicação: bat antes de tab coloca b antes de t, e tub antes de bus coloca t antes de b. As duas condições não podem ser satisfeitas, então nenhuma ordem se encaixa.

Entrada: words = ["cooking", "cook"]
Saída: "invalid"
Explicação: cook é o começo de cooking, então vem primeiro em qualquer alfabeto. A lista o coloca em segundo lugar, o que nenhuma ordem das letras pode explicar.

Para ir além

Como você determinaria se a ordem de ajuste é a única?

Dicas

Abra uma de cada vez. Cada uma revela um pouco mais.

0 de 3 abertas

Solução

Cada par de palavras vizinhas fornece no máximo uma regra, na primeira posição em que diferem: a letra x antes da letra y. Uma ordem adequada é uma ordenação topológica dessas regras. Um ciclo, ou uma palavra colocada antes de seu próprio prefixo, torna a lista impossível. Um min-heap que sempre coloca a menor letra disponível fornece a menor ordenação.

Tente todas as ordens das letras

Correta, mas não termina nos maiores testes

Intuição

Teste uma disposição das k letras distintas verificando cada par de palavras vizinhas. Na primeira posição em que diferirem, a letra da primeira palavra deve vir antes; se não houver diferença, a primeira palavra não pode ser mais longa. Percorra as disposições em ordem crescente a partir da alfabética usando a próxima permutação, e a primeira que passar será a menor ordem que se encaixa.

k letras têm k! disposições: 10 resultam em 3.628.800 e 26 em cerca de 4 × 10^26, e cada teste lê até 5 × 10^4 caracteres. Quando nada se encaixa, a busca tenta todas.

Algoritmo

Reúna as letras distintas e ordene-as alfabeticamente.
Anote a posição de cada letra na disposição atual.
Verifique cada par de palavras vizinhas: na primeira posição em que diferirem, a letra da primeira palavra precisa ter uma posição menor; se não houver diferença, a primeira palavra não pode ser mais longa.
Se todos os pares passarem na verificação, retorne a disposição; caso contrário, passe para a próxima maior.
Quando não houver uma próxima disposição, retorne "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 com uma min-heap

Intuição

Em um par de vizinhos, apenas a primeira diferença conta: act antes de cat indica que a vem antes de c, e as letras seguintes nunca são comparadas. Portanto, cada par gera no máximo uma aresta.

O algoritmo de Kahn transforma as arestas em uma ordem: conte as arestas que chegam a cada letra, coloque uma letra cuja contagem seja 0, remova suas arestas de saída e repita. Uma letra em um ciclo sempre mantém uma aresta vinda da letra anterior a ela no ciclo, então nunca é colocada. Se forem colocadas menos letras do que aparecem, a resposta é "invalid".

Mantenha as letras disponíveis em um min-heap e coloque a menor. Qualquer ordem válida começa com uma letra disponível, então essa é a menor primeira letra possível; além disso, colocá-la apenas remove arestas, portanto não bloqueia nenhuma outra letra. No primeiro exemplo, e e t estão disponíveis no início, e e vem primeiro. Uma fila simples fornece uma ordem válida, mas nem sempre a menor.

Algoritmo

Marque todas as letras que aparecem nas palavras.
Para cada par de vizinhas, encontre a primeira posição diferente e adicione a aresta entre as duas letras, uma única vez. Se não houver diferença e a primeira palavra for mais longa, retorne "invalid".
Conte as arestas de entrada e coloque em um min-heap todas as letras marcadas com contagem 0.
Remova a menor letra e acrescente-a. Diminua a contagem de cada letra para a qual ela aponta e coloque no heap as que chegarem a 0.
Retorne as letras ordenadas se todas as letras marcadas tiverem sido colocadas; caso contrário, retorne "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)

Armadilhas e casos extremos

Usar mais de uma regra de um par. Ler a segunda posição de act e cat adiciona c antes de a, e o primeiro exemplo se torna um ciclo falso.
Ignorar a armadilha do prefixo. cooking antes de cook não tem nenhuma letra diferente, então um loop que só lida com diferenças retorna uma ordem.
Deixar de fora letras que não aparecem em nenhuma regra. No primeiro exemplo, nenhuma regra menciona e, mas essa letra deve fazer parte da resposta.
Contar uma regra repetida duas vezes no grau de entrada, mas armazená-la uma vez. A letra nunca chega a 0, e uma lista válida é indicada como um ciclo.
Tratar duas palavras vizinhas iguais como a armadilha do prefixo; uma palavra repetida está em ordem.

Perguntas frequentes3

Qual é a complexidade de tempo do Alien Dictionary?

O(C + k²), em que C é o número total de caracteres e k ≤ 26 é o número de letras distintas. Uma passagem pela lista encontra cada primeira diferença, e o algoritmo de Kahn percorre no máximo k² arestas. A tabela de arestas ocupa espaço O(k²).

Por que comparar apenas palavras vizinhas?

Estar ordenada é uma propriedade transitiva: se cada palavra é menor ou igual à seguinte, a lista inteira está ordenada. Portanto, qualquer regra que você pudesse deduzir de duas palavras distantes já decorre dos pares vizinhos entre elas.

Por que uma palavra antes de seu próprio prefixo é inválida?

Em todo alfabeto, uma palavra vem depois do seu próprio prefixo, porque a comparação fica sem letras na palavra mais curta antes de encontrar uma diferença. É a única maneira de uma lista ser impossível sem que haja um ciclo entre suas regras.

def alienOrder(words):
    # Escreva o código aqui

Teste #1

Teste #2

Teste #3

Argumento

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

Saída Esperada

"etacn"