Group Anagrams

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

La creación de las claves con las letras ordenadas lleva O(n · k log k) para n palabras de hasta k letras, y el trabajo del mapa es O(n · k) . Ordenar las palabras para ordenar la salida añade O(n · k · log n) , que es lo que más contribuye al coste. El espacio es O(n · k) para las claves y los grupos.

MedioHashing Ordenación

+10

Recibes una lista de palabras strs. Dos palabras son anagramas cuando una reordena las letras de la otra, usando cada letra el mismo número de veces. Agrupa cada palabra con todos sus anagramas y devuelve una cadena por grupo: sus palabras en orden alfabético, unidas por espacios individuales. Ordena los grupos alfabéticamente según su primera palabra.

Una palabra repetida aparece 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 con 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 e, i, l, n, s y t una vez cada una. notes, onset, stone y tones comparten e, n, o, s y t. apple no coincide con nada y, como primera palabra, va primero.

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 va primero.

Para ir más allá

Si las palabras pudieran contener cualquier carácter Unicode, ¿qué clave, las letras ordenadas o el recuento de letras, seguiría 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

Calcula una clave a partir de cada palabra por separado que sea igual para todos sus anagramas y diferente para cualquier otra palabra. Las letras de una palabra ordenadas constituyen esa clave, y un mapa hash de claves a grupos reúne los grupos en una sola pasada. Ordena primero las palabras y obtendrás gratis el orden requerido.

Compara cada palabra con cada grupo

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

Intuición

Mantén una lista de grupos y compara cada palabra con la primera palabra de cada grupo. Ser anagramas es una relación transitiva, así que basta con una comparación por grupo para decidir si una palabra pertenece a él. Dos palabras son anagramas cuando tienen la misma longitud y la misma cantidad de cada una de las 26 letras. Ordena primero la entrada: cada grupo se completa entonces en orden alfabético, y los grupos se crean según el orden de su primera palabra.

Cuando no hay dos palabras que sean anagramas, cada palabra se compara con todos los grupos anteriores: 4000 palabras dan aproximadamente 8 × 10^6 comparaciones, cada una con hasta 8 letras y 26 contadores.

Algoritmo

Ordena las palabras alfabéticamente.
Para cada palabra, busca un grupo cuya primera palabra tenga el mismo recuento de letras y añade la palabra. Si ninguno coincide, inicia un grupo nuevo.
Devuelve las palabras de cada grupo unidas por espacios simples, en el orden de creación.

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

Calcula el nombre del grupo a partir de la palabra misma. Ordena las letras de una palabra y cada anagrama produce el mismo texto: listen, silent y enlist se convierten todos en eilnst, mientras que stone se convierte en enost. Dos palabras comparten una forma ordenada exactamente cuando tienen las mismas letras el mismo número de veces, que es la definición de un anagrama. Un mapa hash de claves a listas de palabras agrupa todo en una sola pasada, y ninguna palabra se compara con otra de un grupo distinto.

El orden se obtiene ordenando primero la entrada, como antes: cada lista se completa alfabéticamente, y una clave entra en el mapa cuando llega la primera palabra de su grupo. Un mapa que conserva el orden de inserción devuelve los grupos en ese orden; de lo contrario, conserva los grupos en una lista y asigna a cada clave su índice.

Ordenar la entrada cuesta unas 5 × 10^4 comparaciones de palabras para 4000 palabras, en lugar de 8 × 10^6.

Algoritmo

Ordena las palabras alfabéticamente.
Para cada palabra, construye 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

Ordenar los grupos por clave en lugar de por la primera palabra. Para ["cab", "bad"], las claves abc y abd ponen cab primero, pero bad debería ir primero.
Recopilar las palabras en un conjunto. ["b", "a", "b"] debe dar b b; un conjunto conserva una sola copia.
Una clave formada solo por las letras distintas. ab y aabb usan las mismas dos letras, pero no son anagramas.
Ordenar cada grupo, pero no la entrada, y no ordenar los grupos. Así, el orden de inserción sigue el orden de entrada, no el de las primeras palabras.

Preguntas frecuentes3

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

La creación de las claves con las letras ordenadas lleva O(n · k log k) para n palabras de hasta k letras, y el trabajo del mapa es O(n · k). Ordenar las palabras para ordenar la salida añade O(n · k · log n), que es lo que más contribuye al coste. El espacio es O(n · k) para las claves y los grupos.

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

Una clave de conteo, los recuentos 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 8 letras o menos, la ordenación es igual de rápida. Ambas claves son exactas: dos palabras tienen los mismos recuentos si y solo si tienen las mismas letras ordenadas.

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

Distintas letras pueden sumar el mismo total: a + d es igual a b + c, así que ad y bc compartirían un grupo. Un producto de un número primo por letra es exacto, pero con 101 para la z, una palabra de diez z desborda un entero de 64 bits.

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

Prueba #1

Prueba #2

Prueba #3

Argumento

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

Salida Esperada

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