Valid Anagram

Q: ¿Cuál es la complejidad temporal de Valid Anagram?

Contar letras lleva un tiempo O(n) y un espacio adicional O(1) , porque el arreglo de contadores tiene 26 entradas sin importar lo largas que sean las cadenas. Ordenar ambas cadenas lleva un tiempo O(n log n) y, por lo general, requiere un espacio O(n) para las copias ordenadas.

Q: ¿Es mejor ordenar o contar al comprobar si dos palabras son anagramas?

Contar es más rápido en teoría, O(n) frente a O(n log n) , y puede detenerse en cuanto se use demasiado una letra. Ordenar requiere menos código y funciona con cualquier alfabeto sin cambios. En una entrevista, menciona primero la ordenación y después mejórala usando el conteo.

FácilHashing Ordenación

+10

Dos cadenas son anagramas cuando una es una reordenación de la otra: usan las mismas letras, y cada letra aparece el mismo número de veces. Recibes dos cadenas s y t formadas por letras minúsculas del inglés. Devuelve true si t es un anagrama de s, y false en caso contrario.

Función

isAnagram(s: string, t: string) → boolean

sstring: la primera cadena, letras minúsculas
tstring: la cadena con la que se compara s
Devuelveboolean: true si t usa exactamente las letras de s, cada una el mismo número de veces

Restricciones

1 ≤ s.length, t.length ≤ 2 × 10⁴
s y t contienen solo letras minúsculas del inglés (a a z).
Las dos longitudes pueden diferir.

Ejemplos

Entrada: s = "listen"t = "silent"
Salida: true
Explicación: Ambas palabras contienen una e, una i, una l, una n, una s y una t, así que silent es listen con sus letras reordenadas.

Entrada: s = "aabb"t = "abbb"
Salida: false
Explicación: Las longitudes coinciden y ambas usan solo a y b, pero aabb tiene dos a y abbb tiene una. Las cantidades tienen que coincidir, no solo las letras.

Entrada: s = "cat"t = "cast"
Salida: false
Explicación: cast tiene cuatro letras y cat tiene tres, así que ninguna reorganización de cat puede formar esa palabra.

+19 pruebas ocultas al enviar

Para ir más allá

¿Y si las cadenas pudieran contener cualquier carácter Unicode en lugar de a a z? ¿Cómo cambiarías el conteo?

Pistas

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

0 de 3 abiertas

Solución

Un anagrama conserva la cantidad de cada letra y descarta el orden. Así que necesitas un resumen de cada cadena que olvide dónde estaban las letras, pero recuerde cuántas hay de cada una. Ordenar crea ese resumen en O(n log n); una tabla de 26 contadores lo crea en una sola pasada.

Ordena ambas cadenas

Intuición

Ordenar coloca las letras de una cadena en orden alfabético y borra dónde empezó cada una. listen se ordena como eilnst, y lo mismo ocurre con silent, así que son anagramas. aabb sigue siendo aabb y abbb sigue siendo abbb; difieren en el índice 1, así que no son anagramas.

La prueba funciona en ambas direcciones. Si t es una reorganización de s, ambas contienen las mismas letras el mismo número de veces, así que ordenarlas produce la misma secuencia. Si las secuencias ordenadas son iguales, t usa exactamente las letras de s.

Compara primero las longitudes: las cadenas de distinta longitud nunca son anagramas, así que te saltas ambos ordenamientos. Ordenar cuesta O(n log n) de tiempo, y la mayoría de los lenguajes ordenan una copia de los caracteres, lo que requiere O(n) de espacio adicional. Con n = 2 × 10^4, esto es rápido, pero el método de conteo requiere menos trabajo.

Algoritmo

Si las longitudes de s y t son diferentes, devuelve false.
Copia los caracteres de cada cadena en un array.
Ordena ambos arrays.
Devuelve true si los arrays ordenados son iguales, elemento por elemento.

def isAnagram(s, t):
    if len(s) != len(t):
        return False
    return sorted(s) == sorted(t)

Cuenta cada letra

Intuición

Solo pueden aparecer 26 letras, así que mantén un contador por cada letra en un array de 26 elementos, con el índice 0 para a y el índice 25 para z. El índice de una letra es su código de carácter menos el código de a. Recorre s y suma 1 al contador de cada letra; después, recorre t y resta 1.

Puedes detenerte antes: un contador por debajo de 0 significa que t ha usado esa letra más veces de las que aparece en s. Para aabb y abbb, después de recorrer s, los contadores indican a: 2 y b: 2. Después, t toma b tres veces; la tercera vez hace que b llegue a -1, y devuelves false en ese mismo momento.

¿Por qué basta con que «ningún contador haya quedado negativo»? Las longitudes son iguales, así que los contadores suman 0 después de recorrer ambas cadenas. Si ninguno es negativo, un contador positivo no tendría con qué compensarse, así que todos los contadores son 0 y las cantidades coinciden. Por eso es necesaria la comprobación de longitud; no es solo un atajo.

Se lee cada cadena una vez, lo que requiere un tiempo de O(n). El array siempre contiene 26 números, sea cual sea la longitud, así que el espacio adicional es O(1).

Algoritmo

Si las longitudes de s y t son diferentes, devuelve false.
Crea un array de 26 ceros.
Por cada letra de s, suma 1 a su contador.
Por cada letra de t, resta 1 a su contador; si baja de 0, devuelve false.
Devuelve true.

def isAnagram(s, t):
    if len(s) != len(t):
        return False
    counts = [0] * 26  # counts[0] is 'a', counts[25] is 'z'
    for ch in s:
        counts[ord(ch) - ord("a")] += 1
    for ch in t:
        index = ord(ch) - ord("a")
        counts[index] -= 1
        if counts[index] < 0:
            return False  # t uses this letter more often than s
    return True

Errores comunes y casos límite

La mayoría de las respuestas incorrectas se deben a comprobar qué letras aparecen en lugar de cuántas veces aparecen, o a omitir la comprobación de longitud.

Comparar los conjuntos de letras. aabb y abbb usan exactamente a y b, pero no son anagramas.
Comprobar que cada letra de t aparezca en algún lugar de s sin tacharla. aab y abb pasan esa prueba en ambas direcciones.
Omitir la comprobación de longitud en la versión que cuenta. Con s = ab y t = a, ningún contador baja de 0, así que el código devolvería true incorrectamente.
Usar el código de carácter sin modificar para indexar el arreglo de contadores. a es 97, muy por encima del final de un arreglo de 26 elementos; primero resta el código de a. En Lua y R, suma 1, ya que sus arreglos comienzan en el índice 1.

Preguntas frecuentes4

¿Cuál es la complejidad temporal de Valid Anagram?

Contar letras lleva un tiempo O(n) y un espacio adicional O(1), porque el arreglo de contadores tiene 26 entradas sin importar lo largas que sean las cadenas. Ordenar ambas cadenas lleva un tiempo O(n log n) y, por lo general, requiere un espacio O(n) para las copias ordenadas.

¿Es mejor ordenar o contar al comprobar si dos palabras son anagramas?

Contar es más rápido en teoría, O(n) frente a O(n log n), y puede detenerse en cuanto se use demasiado una letra. Ordenar requiere menos código y funciona con cualquier alfabeto sin cambios. En una entrevista, menciona primero la ordenación y después mejórala usando el conteo.

¿Cómo compruebas los anagramas que contienen caracteres Unicode?

Reemplaza el arreglo de 26 contadores por un mapa hash que asocie cada carácter con su conteo. Suma 1 por cada carácter de s, resta 1 por cada carácter de t y comprueba que todos los conteos terminen en 0. Lee las cadenas carácter por carácter, no byte por byte, para que un carácter almacenado en varios bytes cuente una sola vez.

¿Por qué usar un solo arreglo de contadores en lugar de dos?

También funcionan dos arreglos, uno por cada cadena: cuenta cada cadena y después compara los arreglos. Un arreglo que aumenta para s y disminuye para t usa la mitad de memoria y te permite devolver false en cuanto un contador se vuelve negativo, sin un bucle final de comparación.

Python

def isAnagram(s, t):
    # Escribe el código aquí

Casos de prueba

Caso 1

Caso 2

Caso 3

Entrada

s = "listen"
t = "silent"

Esperado

true