Alien Dictionary

+10

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

Retorne as letras que aparecem nas palavras como uma única string na ordem do alfabeto. Quando várias ordens forem compatíveis com a lista, retorne aquela que vem primeiro na ordem alfabética comum. Quando nenhuma ordem for compatí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
Toda palavra contém apenas letras minúsculas do inglês.
A mesma palavra pode aparecer mais de uma vez. FORMATO DE SAÍDA OBRIGATÓRIO: [Seu conteúdo traduzido aqui]

Exemplos

Entrada: words = ["tea", "ten", "ate", "act", "cat"]
Saída: "etacn"
Explicação: tea e ten diferem primeiro em a e n, então a vem antes de n. Os outros pares indicam que t vem antes de a, t vem antes de c e a vem antes de c. Nenhuma regra menciona e, então a menor ordem o coloca primeiro, depois t, depois a, depois c e n, que estão ambos livres nesse momento, com c primeiro.

Entrada: words = ["bat", "tab", "tub", "bus"]
Saída: "invalid"
Explicação: bat antes de tab coloca b antes de t, tab antes de tub coloca a antes de u, e tub antes de bus coloca t antes de b. b antes de t e t antes de b não podem ser verdade ao mesmo tempo, então nenhuma ordem se encaixa.

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

+20 testes ocultos ao enviar

Para ir além

Como você verificaria 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

A lista esconde seu alfabeto nos pontos em que palavras vizinhas diferem pela primeira vez. Cada um desses pontos fornece uma regra: a letra x vem antes da letra y, e as regras formam um grafo direcionado sobre as letras. Uma ordem válida é uma ordenação topológica desse grafo. Há duas situações que tornam a lista impossível: um ciclo entre as regras e uma palavra posicionada antes de seu próprio prefixo. Escolher a menor letra disponível em cada etapa, usando um min-heap, produz a menor ordem válida.

Tente todas as ordens das letras

Correta, mas não termina nos maiores testes

Intuição

A resposta é algum arranjo das k letras distintas. Você pode testar diretamente um arranjo: a lista se encaixa nele quando cada par de palavras vizinhas está em ordem de acordo com ele. Compare as duas palavras na primeira posição em que elas diferem; a letra da primeira palavra deve vir antes no arranjo. Se elas nunca diferirem, a primeira palavra não deve ser mais longa. Basta verificar as palavras vizinhas, porque a ordenação é uma cadeia: se cada palavra é menor ou igual à seguinte, a lista inteira está ordenada.

Agora percorra os arranjos do menor para o maior. Comece pelas letras em ordem alfabética, que formam o menor arranjo de todos, e avance para o próximo arranjo maior a cada vez (a próxima permutação). O primeiro arranjo que passar no teste é a menor ordem que se encaixa. Se nenhum passar, retorne "invalid".

Isso está correto, mas é inviável com entradas reais. k letras têm k! arranjos: 5 letras dão 120, 10 dão 3.628.800, e as 26 dão cerca de 4 × 10^26. Cada teste lê a lista inteira, com C caracteres ao todo e até 5 × 10^4. Nos testes grandes, a menor ordem que se encaixa começa com f ou z, então um número astronômico de arranjos vem antes dela; e, quando nada se encaixa, a busca precisa testar todos.

Algoritmo

Reúna as letras distintas e ordene-as alfabeticamente.
Registre a posição de cada letra (sua classificação) na disposição atual.
Verifique cada par de palavras vizinhas: na primeira posição diferente, a letra da primeira palavra precisa ter a classificação menor; se não houver posição diferente, a primeira palavra não deve ser mais longa.
Se todos os pares forem aprovados, retorne a disposição. Caso contrário, passe para a próxima disposição 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 heap mínima

Intuição

Leia as regras diretamente da lista, em vez de tentar adivinhar a ordem. Pegue duas palavras vizinhas e encontre a primeira posição em que elas diferem. tea e ten coincidem em t e e e diferem em a e n, então a vem antes de n. Essa é toda a informação que o par fornece. As letras após a primeira diferença não dizem nada: act vem antes de cat porque a vem antes de c, e o c e o t que vêm depois em act nunca são comparados com o a e o t de cat. Portanto, cada par fornece no máximo uma regra, uma aresta de uma letra para outra.

Um par sem nenhuma posição diferente é a armadilha do prefixo. Uma palavra é o início da outra, e a mais curta precisa vir primeiro em qualquer alfabeto. cook antes de cooking está correto e não fornece nenhuma regra. cooking antes de cook nunca pode ser ordenado, então retorne "invalid" imediatamente. Um loop que apenas procura letras diferentes não encontra nada nesse par e continua para retornar uma ordem para uma lista que nenhum alfabeto pode produzir.

Agora você precisa de uma ordem das letras que respeite todas as arestas, uma ordenação topológica. O algoritmo de Kahn constrói uma. Conte as arestas que apontam para cada letra (seu grau de entrada), coloque uma letra cuja contagem seja 0, remova as arestas que saem dela e repita. Uma letra em um ciclo sempre mantém uma aresta da letra anterior no ciclo, então sua contagem nunca chega a 0 e ela nunca é colocada. Se forem colocadas menos letras do que as que aparecem nas palavras, há um ciclo, e a resposta é "invalid".

Para obter a menor ordem, mantenha as letras cuja contagem é 0 em um min-heap e sempre coloque a menor. Essa escolha gulosa é segura. A primeira letra de qualquer ordem válida tem grau de entrada 0, então a menor letra disponível é a menor primeira letra possível. Colocá-la remove arestas e nunca bloqueia outra letra: toda letra que já estava disponível continua disponível. O mesmo argumento se aplica então à segunda posição, e assim por diante. No primeiro exemplo, e e t estão disponíveis no início, e e vem primeiro. Uma fila comum também produziria uma ordem válida, mas nem sempre a menor.

O custo é uma passagem pela lista, com C caracteres no total, para encontrar as primeiras diferenças. Com k ≤ 26 letras, há no máximo k² arestas, armazenadas em uma tabela k por k para que uma regra repetida seja armazenada uma única vez, e o heap nunca contém mais de k letras. Isso representa tempo O(C + k²), alguns milissegundos nos testes maiores.

Algoritmo

Marque cada letra que aparece nas palavras.
Para cada par de palavras vizinhas, encontre a primeira posição diferente. Se houver uma, adicione a aresta da letra da primeira palavra para a letra da segunda palavra, uma vez. Se não houver e a primeira palavra for mais longa, retorne "invalid".
Conte as arestas de entrada de cada letra e insira em uma min-heap cada letra que aparece e tem contagem 0.
Remova a menor letra e acrescente-a. Diminua a contagem de cada letra para a qual ela aponta e insira aquelas cuja contagem chegar a 0.
Se menos letras forem colocadas do que as que aparecem, retorne "invalid". Caso contrário, retorne as 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)

Armadilhas e casos extremos

A maioria das respostas erradas aqui passa despercebida: uma regra interpretada incorretamente ainda produz alguma ordem, só que a ordem errada.

Considerar mais de uma regra de um par. Só conta a primeira posição diferente. act antes de cat indica que a vem antes de c e não diz nada sobre as letras seguintes.
Não perceber a armadilha do prefixo. cooking antes de cook não tem nenhuma letra diferente, então um loop que só trata diferenças não vê nada e retorna uma ordem. A resposta é "invalid".
Deixar de fora letras que não aparecem em nenhuma regra. No primeiro exemplo, nenhuma regra menciona e, mas ela pertence à resposta, e a menor ordem a coloca primeiro.
Usar uma fila comum em vez de um min-heap. O algoritmo de Kahn com uma fila retorna uma ordem válida, mas o contrato pede a menor.
Contar uma regra repetida duas vezes no grau de entrada, mas armazená-la apenas uma vez no grafo. Assim, a letra nunca chega a 0, e uma lista válida é identificada como um ciclo. Armazene cada regra uma vez ou adicione e remova a mesma quantidade de vezes.
Tratar duas palavras iguais consecutivas como a armadilha do prefixo. Uma palavra seguida pela mesma palavra está em ordem; somente uma palavra mais longa antes de seu próprio prefixo é impossível.

Perguntas frequentes4

Qual é a complexidade de tempo do Dicionário Alienígena?

O(C + k²), em que C é o número total de caracteres nas palavras e k ≤ 26 é o número de letras distintas. Uma passagem pela lista encontra a primeira diferença de cada par de palavras vizinhas, e o algoritmo de Kahn percorre no máximo k² arestas. O min-heap acrescenta O(k log k), o que é pouco em comparação com o restante. A tabela de arestas ocupa O(k²) de espaço.

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. Comparar todos os pares de palavras não acrescenta nenhuma informação e custa O(n²) comparações, em vez de n-1.

Por que escolher a menor letra disponível resulta na menor ordenação?

Qualquer ordenação válida precisa começar com uma letra para a qual nenhuma regra aponta. Portanto, a menor dessas letras é a menor primeira letra possível, e colocá-la apenas remove arestas, então todas as outras letras disponíveis continuam disponíveis. Repetir o argumento em cada posição constrói a menor ordenação letra por letra. Um min-heap fornece a menor letra disponível em O(log k).

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

Em qualquer alfabeto, uma palavra vem depois de seu próprio prefixo, porque a comparação fica sem letras na palavra mais curta antes de encontrar uma diferença. Portanto, cooking antes de cook está fora de ordem, quaisquer que sejam as letras, e nenhuma regra pode corrigir isso. É a única maneira de uma lista ser impossível sem haver nenhum ciclo entre suas regras.

Python

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

Casos de teste

Caso 1

Caso 2

Caso 3

Entrada

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

Esperado

"etacn"