Count Vowels

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

Es O(n) , donde n es la longitud de la cadena, porque cada carácter se comprueba una vez y cada comprobación compara como máximo cinco letras. El espacio adicional es O(1) : un contador y el conjunto fijo de vocales.

Q: ¿Es y una vocal en este problema?

No. En la ortografía inglesa, y a veces actúa como vocal, como en rhythm , pero los problemas de programación casi siempre definen las vocales como a , e , i , o y u , y este también lo hace. Si un problema incluye y , añádela a las letras que compruebas.

PrincipianteArrays y cadenas

+10

Recibes una cadena s formada por letras inglesas. Cuenta cuántos de sus caracteres son vocales y devuelve ese número. Las vocales son a, e, i, o y u, en minúscula o mayúscula. La letra y no cuenta.

Función

countVowels(s: string) → integer

sstring: la cadena de letras inglesas que se va a analizar
Devuelveinteger: el número de vocales en s, tanto mayúsculas como minúsculas

Restricciones

1 ≤ s.length ≤ 5 × 10⁴
s contiene solo letras inglesas (a a z, A a Z).

Ejemplos

Entrada: s = "Interview"
Salida: 4
Explicación: Las vocales son I, e, i y e. La I mayúscula cuenta igual que una minúscula, así que la respuesta es 4.

Entrada: s = "rhythm"
Salida: 0
Explicación: rhythm no tiene a, e, i, o ni u. Su y suena como una vocal, pero no está en la lista, así que la respuesta es 0.

+18 pruebas ocultas al enviar

Para ir más allá

¿Puedes devolver cuántas veces aparece cada una de las cinco vocales, leyendo la cadena solo una vez?

Pistas

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

0 de 3 abiertas

Solución

Contar requiere recorrer la cadena una vez con un contador. Las únicas decisiones son cómo comprobar si un carácter es una vocal y qué hacer con las mayúsculas. Convierte cada carácter a minúscula y compáralo con las cinco vocales; cada carácter requiere una cantidad constante de trabajo.

Cuenta cada vocal en su propia pasada

Intuición

Divide la pregunta en diez preguntas más pequeñas: cuántas a hay, cuántas e, y así sucesivamente hasta U. Cada una de esas cantidades es un recuento simple. Recorre la cadena y suma 1 cada vez que el carácter sea igual a la letra que buscas; después, suma los diez recuentos.

Cada vocal de s es exactamente una de las diez letras de aeiouAEIOU, así que se cuenta exactamente una vez, y ninguna consonante es igual a ninguna de ellas. Para Interview, el recorrido para e encuentra 2, el recorrido para i encuentra 1, el recorrido para I encuentra 1 y los otros siete recorridos no encuentran nada: 4 en total.

La cadena se lee diez veces, lo que supone aproximadamente 10n comparaciones. Sigue siendo O(n), porque diez es una constante, pero para 5 × 10^4 caracteres significa 5 × 10^5 comparaciones, mientras que un solo recorrido leería cada carácter una vez.

Algoritmo

Establece total = 0.
Toma las diez letras aeiouAEIOU de una en una.
Para cada letra, recorre toda la cadena y suma 1 a total cada vez que un carácter sea igual a ella.
Después de las diez pasadas, devuelve total.

def countVowels(s):
    total = 0
    for vowel in "aeiouAEIOU":
        total += s.count(vowel)  # one pass over s for this letter
    return total

Una pasada con una comprobación de minúsculas

Intuición

Dales la vuelta a los bucles. Lee la cadena una vez y, por cada carácter, hazte una pregunta: ¿es una vocal? Para cubrir ambos casos con una sola comprobación, convierte primero el carácter a minúscula. I se convierte en i y E en e, mientras que las consonantes siguen siendo consonantes, así que solo comparas con las cinco letras a, e, i, o y u.

La comprobación tarda un tiempo constante: un switch con cinco letras, una búsqueda en un conjunto o una búsqueda en la cadena de cinco letras aeiou. Al recorrer Interview, el contador aumenta en I, e, i y e, y termina en 4.

Cada carácter se lee una vez, así que el tiempo es O(n). La memoria corresponde al contador y a las cinco vocales: espacio O(1).

Algoritmo

Establece count = 0.
Recorre la cadena un carácter a la vez.
Convierte el carácter a minúscula.
Si es a, e, i, o o u, suma 1 a count.
Devuelve count.

def countVowels(s):
    vowels = set("aeiou")
    count = 0
    for ch in s:
        if ch.lower() in vowels:
            count += 1
    return count

Errores comunes y casos límite

La tarea cabe en unas pocas líneas, y los errores se deben a casos que la primera comprobación pasa por alto.

Comprobar solo las minúsculas. Comparar únicamente con aeiou pasa por alto la I mayúscula de Interview y devuelve 3. Convierte el carácter a minúscula o enumera las diez letras.
Contar la y. En este problema, la y nunca es una vocal, así que rhythm da 0.
Tratar el índice 0 como una coincidencia fallida. "aeiou".indexOf('a') es 0, lo cual sí es una coincidencia. Comprueba si el valor es -1 o, en PHP, compara strpos con false usando !==, porque allí 0 == false.
Llamar a strlen(s) en la condición del bucle en C. Recorre toda la cadena en cada iteración, así que 5 × 10^4 caracteres cuestan alrededor de 2.5 × 10^9 pasos. Detente en el terminador '\0' o calcula la longitud una vez antes del bucle.

Preguntas frecuentes4

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

Recorre la cadena una vez con un contador. Convierte cada carácter a minúscula y comprueba si es a, e, i, o o u; si lo es, suma 1. Cuando termine el bucle, el contador tendrá la respuesta.

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

Es O(n), donde n es la longitud de la cadena, porque cada carácter se comprueba una vez y cada comprobación compara como máximo cinco letras. El espacio adicional es O(1): un contador y el conjunto fijo de vocales.

¿Es y una vocal en este problema?

No. En la ortografía inglesa, y a veces actúa como vocal, como en rhythm, pero los problemas de programación casi siempre definen las vocales como a, e, i, o y u, y este también lo hace. Si un problema incluye y, añádela a las letras que compruebas.

¿La comprobación de vocales debería usar un conjunto, una instrucción switch o una búsqueda en una cadena?

Con cinco letras, las tres requieren un tiempo constante por carácter, y la diferencia de velocidad entre ellas es demasiado pequeña como para importar. Elige la que se lea mejor en tu lenguaje: un switch en C, C++ o Go, un conjunto o una búsqueda en una cadena en Python, JavaScript o Ruby.

Python

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

Casos de prueba

Caso 1

Caso 2

Entrada

s = "Interview"

Esperado