Count Vowels

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

O(n) , donde n es la longitud de la cadena, porque cada carácter se comprueba una vez frente a 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

Dada una cadena s de letras inglesas, devuelve cuántos de sus caracteres son vocales. 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 en inglés que se va a analizar
Devuelveinteger: el número de vocales en s, mayúsculas y minúsculas juntas

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 como 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, y y no está en la lista, así que la respuesta es 0.

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

Lee la cadena una vez con un contador. Convierte cada carácter a minúscula para que una sola comprobación de las cinco vocales cubra ambos casos.

Cuenta cada vocal en su propia pasada

Intuición

Cuenta cada una de las diez letras de aeiouAEIOU recorriendo la cadena por separado y después suma los diez recuentos. Cada vocal coincide exactamente con una de las diez letras, así que se cuenta una vez, y ninguna consonante coincide con ninguna de ellas.

La cadena se lee diez veces. Eso sigue siendo O(n), pero para 5 × 10^4 caracteres significa 5 × 10^5 comparaciones, mientras que una sola pasada lee cada carácter una vez.

Algoritmo

Establece total = 0.
Toma las diez letras aeiouAEIOU una a la vez.
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

Lee la cadena una vez y pregúntate si cada carácter es una vocal. Convertirla primero a minúsculas transforma I en i y deja las consonantes como consonantes, así que comparas con cinco letras en lugar de diez.

La comprobación lleva tiempo constante: un switch, una búsqueda en un conjunto o una búsqueda en la cadena aeiou. Cada carácter se lee una vez y solo se almacena un contador: tiempo O(n), 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

Revisar solo las minúsculas. Comparar únicamente con aeiou no detecta la I mayúscula de Interview y devuelve 3.
Contar la y. Aquí nunca es una vocal, así que rhythm da 0.
Considerar el índice 0 como ausencia. "aeiou".indexOf('a') es 0, lo que sí es una coincidencia. Comprueba si 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. Vuelve a recorrer la cadena en cada paso, así que 5 × 10^4 caracteres cuestan unos 2.5 × 10^9 pasos.

Preguntas frecuentes3

¿Cómo cuentas las vocales de una cadena?

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

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

O(n), donde n es la longitud de la cadena, porque cada carácter se comprueba una vez frente a 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.

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

Prueba #1

Prueba #2

Argumento

s = "Interview"

Salida Esperada