Group Anagrams

Q: Qual é a complexidade de tempo para agrupar anagramas?

A criação das chaves com letras ordenadas leva O(n · k log k) para n palavras com até k letras, e o trabalho com o mapa é O(n · k) . Ordenar as palavras para ordenar a saída adiciona O(n · k · log n) , que é o fator dominante. O espaço é O(n · k) para as chaves e os grupos.

MédioHashing Ordenação

+10

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

Uma palavra repetida aparece 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 e, i, l, n, s e t uma vez cada. notes, onset, stone e tones compartilham e, n, o, s e t. apple não corresponde a nada e, por ser a primeira palavra, fica à frente.

Entrada: strs = ["race", "arc", "care", "car", "acre"]
Saída: ["acre care race", "arc car"]
Explicação: acre, care e race compartilham a, c, e e r. 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.

Para ir além

Se as palavras pudessem conter quaisquer caracteres Unicode, qual chave — letras ordenadas ou contagens de letras — ainda funcionaria, e o que você mudaria nela?

Dicas

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

0 de 3 abertas

Solução

Calcule uma chave a partir de cada palavra que seja igual para todos os seus anagramas e diferente para qualquer outra palavra. As letras de uma palavra em ordem alfabética formam essa chave, e um mapa hash de chave para grupo reúne os grupos em uma única passagem. Ordene as palavras primeiro e a ordem necessária virá naturalmente.

Compare cada palavra com cada grupo

Correta, mas não termina nos maiores testes

Intuição

Mantenha uma lista de grupos e compare cada palavra com a primeira palavra de cada grupo. Ser anagramas é uma relação transitiva, então uma comparação por grupo determina a associação. Duas palavras são anagramas quando têm o mesmo comprimento e a mesma quantidade de cada uma das 26 letras. Ordene a entrada primeiro: cada grupo será preenchido em ordem alfabética, e os grupos serão criados na ordem de sua primeira palavra.

Quando não há duas palavras que sejam anagramas, cada palavra precisa ser comparada com todos os grupos anteriores: 4000 palavras fazem cerca de 8 × 10^6 comparações, cada uma envolvendo até 8 letras e 26 contadores.

Algoritmo

Ordene as palavras alfabeticamente.
Para cada palavra, encontre um grupo cuja primeira palavra tenha a mesma contagem de letras e adicione a palavra. Se nenhum corresponder, inicie um novo grupo.
Retorne as palavras de cada grupo unidas por espaços simples, na ordem em que os grupos 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

Calcule o nome do grupo a partir da própria palavra. Ordene as letras de uma palavra, e cada anagrama resulta no 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 o mesmo número de vezes, que é a definição de anagrama. Um mapa hash de chave para lista de palavras agrupa tudo em uma única passagem, e nenhuma palavra é comparada com outra do grupo.

A ordem vem da ordenação da entrada primeiro, como antes: cada lista é preenchida em ordem alfabética, e uma chave entra no mapa quando chega a primeira palavra do grupo. Um mapa que mantém a ordem de inserção retorna os grupos nessa ordem; caso contrário, mantenha os grupos em uma lista e mapeie cada chave para seu índice.

Ordenar a entrada custa cerca de 5 × 10^4 comparações de palavras para 4000 palavras, em vez de 8 × 10^6.

Algoritmo

Ordene as palavras alfabeticamente.
Para cada palavra, crie sua chave ordenando suas letras.
Procure a chave em um mapa de 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

Ordenar os grupos pela chave em vez de pela primeira palavra. Para ["cab", "bad"], as chaves abc e abd colocam cab primeiro, mas bad deveria vir primeiro.
Coletar as palavras em um conjunto. ["b", "a", "b"] deve resultar em b b; um conjunto mantém apenas uma cópia.
Uma chave criada apenas com as letras distintas. ab e aabb usam as mesmas duas letras, mas não são anagramas.
Ordenar cada grupo, mas não a entrada, e não ordenar os grupos. Assim, a ordem de inserção segue a entrada, não as primeiras palavras.

Perguntas frequentes3

Qual é a complexidade de tempo para agrupar anagramas?

A criação das chaves com letras ordenadas leva O(n · k log k) para n palavras com até k letras, e o trabalho com o mapa é O(n · k). Ordenar as palavras para ordenar a saída adiciona O(n · k · log n), que é o fator dominante. O espaço é O(n · k) para as chaves e os grupos.

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

Uma chave de contagem, os 26 números de ocorrências das letras escritos como texto, como 1#0#2#…, leva O(k) em vez de O(k log k), então é mais eficiente para palavras longas. Com 8 letras ou menos, a ordenação é igualmente rápida. Ambas as chaves são exatas: 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 somar o mesmo total: a + d é igual a b + c, então ad e bc compartilhariam um grupo. Um produto de um número primo por letra é exato, mas, com 101 para z, uma palavra com dez z's excede o limite de um inteiro de 64 bits.

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

Teste #1

Teste #2

Teste #3

Argumento

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

Saída Esperada

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