Remove Vowels

Q: ¿Cómo se eliminan las vocales de una cadena?

Recorre la cadena una vez y copia cada letra que no sea a , e , i , o o u (en mayúsculas o minúsculas) en un generador o una lista. Únelas en una cadena al final. El orden y las mayúsculas y minúsculas de las letras conservadas se mantienen tal como estaban.

Q: ¿Cuál es la complejidad temporal de eliminar las vocales?

Una pasada requiere un tiempo de O(n) , porque cada carácter se somete a una comprobación de vocales de tiempo constante. La salida ocupa un espacio de O(n) en el peor caso, cuando s no tiene vocales. Llamar a replace una vez por cada vocal también requiere O(n) , pero lee la cadena diez veces.

Q: ¿Puedes eliminar las vocales con una expresión regular?

Sí. Reemplazar el patrón [aeiouAEIOU] por una cadena vacía lo hace en una sola llamada en la mayoría de los lenguajes. Se ejecuta en O(n) , igual que el bucle, pero los entrevistadores suelen pedirte que escribas el bucle para que puedan ver la comprobación de las vocales y cómo construyes el resultado.

PrincipianteArrays y cadenas

+10

Recibes una cadena s formada por letras inglesas. Devuelve la cadena que obtienes al eliminar todas las vocales. Las vocales son a, e, i, o y u, en minúscula o mayúscula; aquí, y no es una vocal. Las letras que quedan conservan su orden y su uso de mayúsculas y minúsculas.

Función

removeVowels(s: string) → string

sstring: la cadena de letras en inglés que hay que limpiar
Devuelvestring: s con todas las vocales eliminadas y las demás letras en su orden original

Restricciones

1 ≤ s.length ≤ 3 × 10⁴
s contiene solo letras del alfabeto inglés (a a z, A a Z).
s contiene al menos una letra que no es una vocal, así que la respuesta nunca está vacía.

Ejemplos

Entrada: s = "Interview"
Salida: "ntrvw"
Explicación: Al eliminar I, e, i y e de Interview, quedan n, t, r, v, w en ese orden. La I mayúscula también es una vocal, así que se elimina.

Entrada: s = "rhythm"
Salida: "rhythm"
Explicación: rhythm no tiene a, e, i, o ni u, así que no se elimina nada. Su y no está en la lista de vocales y se queda.

Entrada: s = "EuropeanUnion"
Salida: "rpnnn"
Explicación: Ocho de las trece letras de EuropeanUnion son vocales, incluidas las mayúsculas E y U. Las cinco consonantes restantes, r, p, n, n, n, mantienen su orden y se leen rpnnn.

+17 pruebas ocultas al enviar

Para ir más allá

¿Y si el texto pudiera contener cualquier letra Unicode, como É u ö? ¿Cuáles de ellas son vocales y cómo cambia tu prueba?

Pistas

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

0 de 3 abiertas

Solución

Eliminar caracteres del medio de una cadena es costoso si lo haces de uno en uno, porque todo lo que queda después del hueco se desplaza. La mejor estrategia es construir la respuesta: recorre la cadena una vez y copia cada letra que no sea una vocal. Los detalles que debes tener en cuenta son las vocales mayúsculas y cómo se ensambla el resultado.

Elimina cada vocal en su propia pasada

Intuición

La mayoría de los lenguajes pueden eliminar todas las apariciones de un carácter de una cadena en una sola llamada: reemplazándolo por nada. Hazlo diez veces, una por cada uno de a e i o u A E I O U, y no quedará ninguna vocal. Las consonantes nunca se tocan, así que conservan su orden y mayúsculas o minúsculas.

Para Interview, la pasada para e da Intrviw, la pasada para i da Intrvw y la pasada para I da ntrvw. Las otras siete pasadas no encuentran nada que eliminar.

Cada pasada lee toda la cadena actual, así que el trabajo es de aproximadamente 10n pasos de caracteres. Eso sigue siendo O(n), porque diez es una constante, pero para 3 × 10^4 letras significa 3 × 10^5 pasos, mientras que un solo recorrido necesita 3 × 10^4.

Algoritmo

Toma las diez letras vocales aeiouAEIOU una a la vez.
Para cada una, reemplaza todas sus apariciones en s por nada.
Después de las diez pasadas, devuelve lo que queda de s.

def removeVowels(s):
    for vowel in "aeiouAEIOU":
        s = s.replace(vowel, "")  # one full pass for this letter
    return s

Una pasada que conserva las consonantes

Intuición

Dale la vuelta a la tarea: en lugar de eliminar las vocales, recoge todo lo demás. Recorre s una vez y, para cada carácter, pregunta si es una de las diez letras vocálicas. Si no lo es, añádelo al resultado. Como añades los caracteres en el orden en que los lees y nunca cambias ninguno, el orden y las mayúsculas y minúsculas de las consonantes quedan exactamente igual que al principio.

Para EuropeanUnion, el recorrido omite E, u, o, e, a, U, i y o, y añade r, p, n, n, n: el resultado es rpnnn.

Cada carácter requiere una comprobación de tiempo constante (una búsqueda en un conjunto, un switch o una búsqueda en una cadena de diez letras), así que el tiempo es O(n). Recoge las letras en un acumulador o una lista y conviértelo en una cadena una sola vez al final; ampliar una cadena inmutable con += haría que se copiara en cada paso. La propia salida ocupa un espacio de O(n).

Algoritmo

Inicia un constructor vacío para el resultado.
Recorre s carácter por carácter.
Si el carácter no es una de las aeiouAEIOU, añádelo al constructor.
Devuelve el constructor como una cadena.

def removeVowels(s):
    vowels = set("aeiouAEIOU")
    kept = []
    for ch in s:
        if ch not in vowels:
            kept.append(ch)
    # Joining a list once avoids rebuilding the string on every character.
    return "".join(kept)

Errores comunes y casos límite

La mayoría de las respuestas incorrectas se deben a la comprobación de vocales o a cómo va creciendo la cadena de resultado.

Olvidar las vocales mayúsculas. Comprobar solo aeiou transforma Interview en Intrvw en vez de ntrvw. Comprueba las diez letras o convierte el carácter a minúscula antes de comprobarlo, y conserva el carácter original en el resultado.
Cambiar las mayúsculas y minúsculas de las letras que se conservan. Si conviertes toda la cadena a minúsculas para simplificar la comprobación, QUEUEING se convierte en qng en vez de QNG. Convierte a minúscula solo la copia que compruebas y añade el carácter original.
Eliminar elementos mientras recorres la cadena hacia delante por índice. Eliminar s[i] desplaza la letra siguiente a la posición i y, después, i++ se la salta, así que aab se convierte en ab. Construye una cadena nueva o recorre la cadena con posiciones de lectura y escritura separadas.
Ampliar una cadena inmutable con += dentro de un bucle. En Java o C#, cada paso copia toda la cadena: aproximadamente 4.5 × 10^8 copias de caracteres para 3 × 10^4 letras. Usa un generador de cadenas o una lista y únelos una sola vez.

Preguntas frecuentes4

¿Cómo se eliminan las vocales de una cadena?

Recorre la cadena una vez y copia cada letra que no sea a, e, i, o o u (en mayúsculas o minúsculas) en un generador o una lista. Únelas en una cadena al final. El orden y las mayúsculas y minúsculas de las letras conservadas se mantienen tal como estaban.

¿Cuál es la complejidad temporal de eliminar las vocales?

Una pasada requiere un tiempo de O(n), porque cada carácter se somete a una comprobación de vocales de tiempo constante. La salida ocupa un espacio de O(n) en el peor caso, cuando s no tiene vocales. Llamar a replace una vez por cada vocal también requiere O(n), pero lee la cadena diez veces.

¿Puedes eliminar las vocales con una expresión regular?

Sí. Reemplazar el patrón [aeiouAEIOU] por una cadena vacía lo hace en una sola llamada en la mayoría de los lenguajes. Se ejecuta en O(n), igual que el bucle, pero los entrevistadores suelen pedirte que escribas el bucle para que puedan ver la comprobación de las vocales y cómo construyes el resultado.

¿Por qué no eliminar las vocales de la cadena directamente?

Eliminar un carácter del medio desplaza todos los caracteres posteriores hacia la izquierda, por lo que muchas eliminaciones pueden costar O(n²). Puedes hacerlo en el mismo lugar en O(n) con dos índices: uno que lee cada carácter y otro que escribe la siguiente letra que se conserva, pero en la mayoría de los lenguajes las cadenas no se pueden modificar, así que crear una cadena nueva es la opción natural.

Python

def removeVowels(s):
    # Escribe el código aquí

Casos de prueba

Caso 1

Caso 2

Caso 3

Entrada

s = "Interview"

Esperado

"ntrvw"