Group Anagrams

+10

Você recebe uma lista de palavras strs. Duas palavras são anagramas quando uma é uma reorganização da outra: as mesmas letras, cada uma usada o mesmo número de vezes. Coloque cada palavra em um grupo com todos os seus anagramas e retorne uma string por grupo: as palavras do grupo em ordem alfabética, separadas por espaços simples. Ordene os grupos alfabeticamente pela primeira palavra.

Uma palavra que aparece duas vezes é listada duas vezes em seu grupo, e uma palavra sem anagramas forma um grupo de uma palavra. Ordem alfabética significa ordem de dicionário: aab vem antes de ab, e ab antes de abc.

Função

groupAnagrams(strs: string-array) → string-array

strsstring-array: as palavras a agrupar, somente letras minúsculas
Retornastring-array: uma string por grupo: suas palavras ordenadas e unidas por espaços, grupos ordenados pela primeira palavra

Restrições

1 ≤ strs.length ≤ 4000
1 ≤ strs[i].length ≤ 8
Cada palavra contém apenas letras minúsculas do inglês.

Exemplos

Entrada: strs = ["listen", "stone", "silent", "notes", "enlist", "onset", "tones", "apple"]
Saída: ["apple", "enlist listen silent", "notes onset stone tones"]
Explicação: enlist, listen e silent usam cada uma as letras e, i, l, n, s e t uma vez. notes, onset, stone e tones compartilham as letras e, n, o, s e t, e apple não corresponde a nenhuma. Em ordem da primeira palavra, os grupos são apple, enlist, notes.

Entrada: strs = ["race", "arc", "care", "car", "acre"]
Saída: ["acre care race", "arc car"]
Explicação: acre, care e race têm a, c, e e r em comum. arc e car não têm e, então formam seu próprio grupo. acre vem antes de arc porque c vem antes de r na segunda letra.

Entrada: strs = ["b", "a", "b"]
Saída: ["a", "b b"]
Explicação: As duas cópias de b são anagramas uma da outra, e ambas permanecem no grupo. a não tem par e vem primeiro.

+15 testes ocultos ao enviar

Para ir além

Suponha que as palavras possam conter quaisquer caracteres Unicode, em vez de apenas 26 letras minúsculas. Qual das duas chaves, letras ordenadas ou contagens de letras, ainda funciona, e o que você mudaria nela?

Dicas

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

0 de 3 abertas

Solução

Comparar cada palavra com todas as outras funciona, mas exige uma comparação completa para cada par. O que resolve o problema é uma chave canônica: um valor que você calcula a partir de uma única palavra, que é igual para todos os seus anagramas e diferente para qualquer outra palavra. As letras de uma palavra em ordem alfabética formam uma chave desse tipo, e um mapa hash de chaves para grupos transforma o agrupamento em uma única passagem. A ordem exigida é obtida de graça se você ordenar as palavras antes de agrupá-las.

Compare cada palavra com todos os grupos

Correta, mas não termina nos maiores testes

Intuição

Serem anagramas é uma relação transitiva: se stone corresponde a notes e notes corresponde a tones, então stone corresponde a tones. Portanto, uma palavra nova nunca precisa ser comparada com todos os membros de um grupo. Compará-la com a primeira palavra do grupo determina se ela pertence a ele.

Para comparar duas palavras, conte as letras. Elas são anagramas quando têm o mesmo comprimento e cada letra aparece o mesmo número de vezes em uma e na outra. Some 1 para cada letra da primeira palavra e subtraia 1 para cada letra da segunda, e verifique se todos os 26 contadores terminam em 0.

Ordene primeiro a entrada, e a ordem se resolve sozinha. As palavras chegam em ordem alfabética, cada uma é adicionada ao final do seu grupo, então todos os grupos permanecem ordenados. Um grupo é criado quando sua primeira palavra em ordem alfabética chega, então os grupos já ficam ordenados pela primeira palavra.

O custo está na varredura. Quando não há duas palavras que sejam anagramas, cada palavra é comparada com todos os grupos anteriores: 4000 palavras geram cerca de 4000 × 3999 / 2 ≈ 8 × 10^6 comparações, cada uma envolvendo até 8 letras e 26 contadores. Isso é lento demais para Python, Lua e R nos maiores testes, e o trabalho cresce com o quadrado da lista, então isso inviabilizaria qualquer linguagem com 10^5 palavras.

Algoritmo

Ordene as palavras em ordem alfabética.
Mantenha uma lista de grupos, cada um contendo uma lista de palavras.
Para cada palavra, procure um grupo cuja primeira palavra tenha a mesma contagem de letras e acrescente a palavra a ele.
Se nenhum grupo corresponder, inicie um novo grupo contendo apenas essa palavra.
Una as palavras de cada grupo com espaços simples e retorne os grupos na ordem em que foram criados.

def is_anagram(a, b):
    # Same length, and every letter appears as often in a as in b.
    if len(a) != len(b):
        return False
    counts = [0] * 26
    for c in a:
        counts[ord(c) - 97] += 1
    for c in b:
        counts[ord(c) - 97] -= 1
    return all(x == 0 for x in counts)


def groupAnagrams(strs):
    # Sort first: each group fills up in alphabetical order,
    # and groups are created in the order of their first word.
    groups = []
    for word in sorted(strs):
        for group in groups:
            if is_anagram(group[0], word):
                group.append(word)
                break
        else:
            groups.append([word])
    return [" ".join(group) for group in groups]

Agrupe por letras ordenadas em um mapa hash

Intuição

Em vez de perguntar a qual grupo uma palavra corresponde, calcule o nome do grupo a partir da própria palavra. Ordene as letras de uma palavra, e todos os seus anagramas terão o mesmo texto: listen, silent e enlist se tornam eilnst, enquanto stone se torna enost. Duas palavras compartilham exatamente a mesma forma ordenada quando contêm as mesmas letras a mesma quantidade de vezes, que é a definição de anagrama. Portanto, a forma ordenada é uma chave canônica para o grupo.

Um mapa hash de chave para lista de palavras agrupa tudo em uma única passagem. Cada palavra custa uma ordenação de no máximo 8 letras e uma busca no mapa, e nunca é comparada com outro grupo.

Para manter a ordem, ordene a entrada antes de agrupar, como na primeira abordagem. As palavras chegam em ordem alfabética, então cada lista é preenchida em ordem, e uma chave entra no mapa quando chega a primeira palavra do grupo. Mapas que mantêm a ordem de inserção (um dict do Python, um Map do JavaScript, um LinkedHashMap do Java, um map do Dart, hashes do Ruby e arrays do PHP) retornam os grupos nessa ordem. Quando o mapa não tem ordem, armazene o índice de cada grupo no mapa e os próprios grupos em uma lista.

Ordenar a entrada exige cerca de n log n comparações de até k letras, aproximadamente 5 × 10^4 comparações de palavras para 4000 palavras, em vez de 8 × 10^6. A construção das chaves adiciona O(n · k log k), o que é pouco em comparação, porque k ≤ 8.

Algoritmo

Ordene as palavras em ordem alfabética.
Para cada palavra, crie sua chave ordenando as letras.
Procure a chave em um mapa hash. Se ela for nova, inicie um grupo vazio para ela, mantendo os grupos na ordem em que forem criados.
Acrescente a palavra ao grupo de sua chave.
Retorne as palavras de cada grupo unidas por espaços simples, com os grupos na ordem de criação.

def groupAnagrams(strs):
    # Sort first: each group fills up in alphabetical order,
    # and groups are created in the order of their first word.
    groups = {}  # key (the letters in sorted order) -> the group's words
    for word in sorted(strs):
        key = "".join(sorted(word))
        groups.setdefault(key, []).append(word)
    # A dict keeps insertion order, so the groups come out by first word.
    return [" ".join(words) for words in groups.values()]

Armadilhas e casos extremos

A agrupação é a parte que as pessoas praticam. A maioria das respostas erradas nesta versão vem da ordem da saída e de chaves que não são únicas.

Ordenar os grupos pela chave em vez de pela primeira palavra. Uma chave é o menor rearranjo de suas letras, não uma das palavras: para ["cab", "bad"], as chaves são abc e abd, o que colocaria cab primeiro, mas, pela primeira palavra, bad vem primeiro.
Coletar palavras em um conjunto. ["b", "a", "b"] deve resultar em b b; um conjunto mantém apenas uma cópia.
Uma chave construída apenas com as letras distintas. ab e aabb usam as mesmas duas letras, mas aabb tem duas de cada, então não são anagramas.
Uma chave que soma os códigos das letras. ad e bc têm a mesma soma, então uma soma agrupa palavras que não compartilham nenhuma letra.
Ordenar cada grupo, mas não a entrada, e depois esquecer de ordenar os grupos. A ordem de inserção passa a ser a ordem da entrada, não a das primeiras palavras.
Juntar manualmente e deixar um espaço no início ou no fim da string de um grupo.

Perguntas frequentes4

Qual é a complexidade de tempo de agrupar anagramas?

Com um mapa hash indexado pelas letras ordenadas, a criação das chaves leva O(n · k log k) para n palavras com até k letras, e o trabalho com o mapa é O(n · k). Esta versão também ordena as palavras para ordenar a saída, o que adiciona O(n · k · log n). O espaço é O(n · k) para as chaves e os grupos.

Uma chave baseada na contagem de letras é mais rápida do que ordenar cada palavra?

Uma chave de contagem, com as contagens das 26 letras escritas como texto, como 1#0#2#…, leva O(k) em vez de O(k log k), então é melhor para palavras longas. Para palavras com no máximo 8 letras, a ordenação é igualmente rápida, e a ordenação alfabética da saída custa mais do que qualquer uma das chaves. Ambas as chaves estão corretas, porque duas palavras têm as mesmas contagens exatamente quando têm as mesmas letras ordenadas.

Por que não usar a soma dos códigos das letras como chave?

Letras diferentes podem resultar no mesmo total: a + d é igual a b + c, então ad e bc ficariam no mesmo grupo. Uma chave deve ser igual para anagramas e diferente para todo o resto, e as letras ordenadas ou a contagem completa de cada letra garantem isso. Multiplicar um número primo por letra também é exato, mas, usando 101 para z, uma palavra com dez z's já ultrapassa o limite de um inteiro de 64 bits.

Por que ordenar a entrada antes de agrupar?

A resposta pede grupos ordenados pela primeira palavra de cada um. Ordenar todas as palavras uma vez produz ambos os resultados: cada grupo recebe suas palavras em ordem alfabética, e um grupo é criado quando sua primeira palavra chega. Ordenar cada grupo depois e, em seguida, os grupos pela primeira palavra de cada um produz o mesmo resultado com mais código.

Python

def groupAnagrams(strs):
    # Escreva o código aqui

Casos de teste

Caso 1

Caso 2

Caso 3

Entrada

strs = ["listen", "stone", "silent", "notes", "enlist", "onset", "tones", "apple"]

Esperado

["apple", "enlist listen silent", "notes onset stone tones"]