Group Anagrams

+10

Recibes una lista de palabras strs. Dos palabras son anagramas cuando una es una reordenación de la otra: las mismas letras, cada una usada el mismo número de veces. Agrupa cada palabra con todos sus anagramas y devuelve una cadena por grupo: las palabras del grupo en orden alfabético, separadas por espacios simples. Ordena los grupos alfabéticamente según su primera palabra.

Si una palabra aparece dos veces, se incluye dos veces en su grupo; y una palabra sin anagramas forma un grupo de una sola palabra. El orden alfabético es el orden del diccionario: aab va antes que ab, y ab antes que abc.

Función

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

strsstring-array: las palabras para agrupar, solo letras minúsculas
Devuelvestring-array: una cadena por grupo: sus palabras ordenadas y unidas por espacios, grupos ordenados por su primera palabra

Restricciones

1 ≤ strs.length ≤ 4000
1 ≤ strs[i].length ≤ 8
Cada palabra contiene únicamente letras minúsculas del inglés.

Ejemplos

Entrada: strs = ["listen", "stone", "silent", "notes", "enlist", "onset", "tones", "apple"]
Salida: ["apple", "enlist listen silent", "notes onset stone tones"]
Explicación: enlist, listen y silent usan cada una e, i, l, n, s y t una vez. notes, onset, stone y tones comparten e, n, o, s y t, y apple no coincide con ninguna. Ordenados por la primera palabra, los grupos son apple, enlist, notes.

Entrada: strs = ["race", "arc", "care", "car", "acre"]
Salida: ["acre care race", "arc car"]
Explicación: acre, care y race comparten a, c, e y r. arc y car no tienen e, así que forman su propio grupo. acre va antes que arc porque c va antes que r en la segunda letra.

Entrada: strs = ["b", "a", "b"]
Salida: ["a", "b b"]
Explicación: Las dos copias de b son anagramas entre sí y ambas permanecen en el grupo. a no tiene pareja y aparece primero.

+15 pruebas ocultas al enviar

Para ir más allá

Supón que las palabras pudieran contener cualquier carácter Unicode en lugar de solo 26 letras minúsculas. ¿Cuál de las dos claves, las letras ordenadas o los recuentos de letras, sigue funcionando y qué cambiarías en ella?

Pistas

Ábrelas de una en una. Cada una revela un poco más.

0 de 3 abiertas

Solución

Comparar cada palabra con todas las demás funciona, pero requiere una comparación completa para cada par. Lo que resuelve el problema es una clave canónica: un valor que se calcula a partir de una sola palabra y que es igual para todos sus anagramas y distinto para cualquier otra palabra. Las letras de una palabra ordenadas alfabéticamente son una clave de este tipo, y un mapa hash de claves a grupos convierte la agrupación en una sola pasada. El orden requerido se obtiene automáticamente si ordenas las palabras antes de agruparlas.

Compara cada palabra con cada grupo

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

Intuición

Ser anagramas es una relación transitiva: si stone coincide con notes y notes coincide con tones, entonces stone coincide con tones. Así que nunca hace falta que una palabra nueva coincida con todos los miembros de un grupo. Compararla con la primera palabra del grupo determina si pertenece a él.

Para comparar dos palabras, cuenta las letras. Son anagramas cuando tienen la misma longitud y cada letra aparece el mismo número de veces en ambas. Suma 1 por cada letra de la primera palabra y resta 1 por cada letra de la segunda, y comprueba que los 26 contadores terminen en 0.

Ordena primero la entrada y el orden se resolverá solo. Las palabras llegan en orden alfabético y cada una se añade al final de su grupo, así que todos los grupos permanecen ordenados. Se crea un grupo cuando llega su palabra alfabéticamente menor, por lo que los grupos ya quedan ordenados según su primera palabra.

El coste está en el recorrido. Cuando no hay dos palabras que sean anagramas, cada palabra se compara con todos los grupos anteriores: 4000 palabras implican unas 4000 × 3999 / 2 ≈ 8 × 10^6 comparaciones, cada una de las cuales examina hasta 8 letras y 26 contadores. Eso es demasiado lento para Python, Lua y R en las pruebas más grandes, y el trabajo crece con el cuadrado de la lista, así que haría fallar a cualquier lenguaje con 10^5 palabras.

Algoritmo

Ordena las palabras alfabéticamente.
Mantén una lista de grupos, cada uno con una lista de palabras.
Para cada palabra, busca un grupo cuya primera palabra tenga las mismas cantidades de letras y añádela a ese grupo.
Si ningún grupo coincide, inicia un grupo nuevo que contenga solo esta palabra.
Une las palabras de cada grupo con espacios simples y devuelve los grupos en el orden en que los creaste.

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]

Agrupa por letras ordenadas en un mapa hash

Intuición

En lugar de preguntar a qué grupo pertenece una palabra, calcula el nombre del grupo a partir de la propia palabra. Ordena las letras de una palabra y todos sus anagramas dan el mismo texto: listen, silent y enlist se convierten en eilnst, mientras que stone se convierte en enost. Dos palabras comparten una forma ordenada exactamente cuando contienen las mismas letras el mismo número de veces, que es la definición de un anagrama. Por lo tanto, la forma ordenada es una clave canónica para el grupo.

Un mapa hash que asocie cada clave con una lista de palabras agrupa todo en una sola pasada. Cada palabra requiere ordenar como máximo 8 letras y hacer una búsqueda en el mapa, y nunca se compara con otra palabra de otro grupo.

Para mantener el orden, ordena la entrada antes de agrupar, como en el primer enfoque. Las palabras llegan en orden alfabético, así que cada lista se va llenando en orden, y una clave entra en el mapa cuando llega la primera palabra de su grupo. Los mapas que mantienen el orden de inserción (un dict de Python, un Map de JavaScript, un LinkedHashMap de Java, un map de Dart, los hashes de Ruby y los arrays de PHP) devuelven los grupos en ese orden. Si el mapa no tiene orden, almacena el índice de cada grupo en el mapa y los propios grupos en una lista.

Ordenar la entrada requiere aproximadamente n log n comparaciones de hasta k letras, unas 5 × 10^4 comparaciones de palabras para 4000 palabras en lugar de 8 × 10^6. La creación de las claves añade O(n · k log k), que es un costo pequeño en comparación porque k ≤ 8.

Algoritmo

Ordena las palabras alfabéticamente.
Para cada palabra, crea su clave ordenando sus letras.
Busca la clave en un mapa hash. Si es nueva, inicia un grupo vacío para ella, manteniendo los grupos en el orden en que los creas.
Añade la palabra al grupo de su clave.
Devuelve las palabras de cada grupo unidas por espacios simples, con los grupos en el orden en que se crearon.

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()]

Errores comunes y casos límite

Agrupar es la parte que hay que practicar. La mayoría de las respuestas incorrectas en esta versión se deben al orden de la salida y a las claves que no son únicas.

Ordenar los grupos por su clave en lugar de por su primera palabra. Una clave es el reordenamiento más pequeño de sus letras, no una de las palabras: para ["cab", "bad"] las claves son abc y abd, lo que pondría cab primero, pero por la primera palabra, bad va primero.
Recopilar las palabras en un conjunto. ["b", "a", "b"] debe dar b b; un conjunto conserva una sola copia.
Una clave construida solo con las letras distintas. ab y aabb usan las mismas dos letras, pero aabb tiene dos de cada una, así que no son anagramas.
Una clave que suma los códigos de las letras. ad y bc tienen la misma suma, así que una suma agrupa palabras que no comparten ninguna letra.
Ordenar cada grupo, pero no la entrada, y luego olvidarse de ordenar los grupos. Entonces el orden de inserción es el de la entrada, no el de las primeras palabras.
Unir a mano y dejar un espacio al principio o al final de la cadena de un grupo.

Preguntas frecuentes4

¿Cuál es la complejidad temporal de agrupar anagramas?

Con un mapa hash cuyas claves son las letras ordenadas, crear las claves toma O(n · k log k) para n palabras de hasta k letras, y el trabajo del mapa es O(n · k). Esta versión también ordena las palabras para ordenar la salida, lo que añade O(n · k · log n). El espacio es O(n · k) para las claves y los grupos.

¿Es más rápida una clave basada en el recuento de letras que ordenar cada palabra?

Una clave de conteo, los conteos de las 26 letras escritos como texto, como 1#0#2#…, tarda O(k) en lugar de O(k log k), así que es más rápida con palabras largas. Con palabras de como máximo 8 letras, la ordenación es igual de rápida, y la ordenación alfabética de la salida cuesta más que cualquiera de las dos claves. Ambas claves son correctas, porque dos palabras tienen los mismos conteos exactamente cuando tienen las mismas letras ordenadas.

¿Por qué no usar la suma de los códigos de las letras como clave?

Distintas letras pueden sumar lo mismo: a + d equivale a b + c, así que ad y bc quedarían en el mismo grupo. Una clave debe ser igual para los anagramas y diferente para todo lo demás, y las letras ordenadas o el recuento completo de cada letra lo garantizan. Multiplicar un número primo por cada letra también es exacto, pero con 101 para la z, una palabra de diez z ya desborda un entero de 64 bits.

¿Por qué ordenar la entrada antes de agruparla?

La respuesta solicita grupos ordenados por su primera palabra. Ordenar todas las palabras una vez proporciona ambas cosas: cada grupo recibe sus palabras en orden alfabético y se crea un grupo cuando llega su primera palabra. Ordenar después cada grupo y luego los grupos por su primera palabra da el mismo resultado con más código.

Python

def groupAnagrams(strs):
    # Escribe el código aquí

Casos de prueba

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"]