Count Vowels

Q: Quelle est la complexité temporelle du comptage des voyelles ?

C’est O(n) , où n est la longueur de la chaîne, car chaque caractère est vérifié une fois et chaque vérification compare au maximum cinq lettres. L’espace supplémentaire est O(1) : un compteur et l’ensemble fixe de voyelles.

Q: Y est-il une voyelle dans ce problème ?

Non. En orthographe anglaise, y joue parfois le rôle d’une voyelle, comme dans rhythm , mais les problèmes de programmation définissent presque toujours les voyelles comme étant a , e , i , o et u , et c’est le cas ici. Si un problème inclut y , ajoute-le aux lettres que tu vérifies.

DébutantTableaux et chaînes

+10

On te donne une chaîne s composée de lettres anglaises. Compte le nombre de ses caractères qui sont des voyelles et renvoie ce nombre. Les voyelles sont a, e, i, o et u, en minuscules ou en majuscules. La lettre y ne compte pas.

Fonction

countVowels(s: string) → integer

sstring: la chaîne de lettres anglaises à parcourir
Renvoieinteger: le nombre de voyelles dans s, majuscules et minuscules réunies

Contraintes

1 ≤ s.length ≤ 5 × 10⁴
s ne contient que des lettres anglaises (a à z, A à Z).

Exemples

Entrée: s = "Interview"
Sortie: 4
Explication: Les voyelles sont I, e, i et e. Le I majuscule compte comme un I minuscule, donc la réponse est 4.

Entrée: s = "rhythm"
Sortie: 0
Explication: rhythm ne contient aucun a, e, i, o ou u. Son y se prononce comme une voyelle, mais il ne figure pas dans la liste, donc la réponse est 0.

+18 tests cachés à la soumission

Pour aller plus loin

Peux-tu renvoyer le nombre de fois que chacune des cinq voyelles apparaît, tout en ne lisant la chaîne qu’une seule fois ?

Indices

Ouvrez-les un par un. Chacun en dévoile un peu plus.

0 sur 3 ouverts

Solution

Le comptage parcourt la chaîne une seule fois à l’aide d’un compteur. Les seules décisions à prendre sont de savoir comment tester si un caractère est une voyelle et quoi faire des majuscules. Convertis chaque caractère en minuscule et compare-le aux cinq voyelles ; chaque caractère demande ainsi une quantité constante de travail.

Comptez chaque voyelle avec un passage distinct

Intuition

Décompose la question en dix questions plus petites : combien y a-t-il de a, combien de e, et ainsi de suite jusqu’à U. Chacune de ces questions revient à faire un simple décompte. Parcours la chaîne et ajoute 1 chaque fois que le caractère correspond à la lettre recherchée, puis additionne les dix décomptes.

Chaque voyelle de s correspond exactement à l’une des dix lettres de aeiouAEIOU, donc elle est comptée exactement une fois, et aucune consonne ne correspond à l’une d’elles. Pour Interview, le passage pour e trouve 2 occurrences, celui pour i en trouve 1, celui pour I en trouve 1, et les sept autres passages ne trouvent rien : 4 au total.

La chaîne est parcourue dix fois, soit environ 10n comparaisons. Cela reste O(n), car dix est une constante, mais pour 5 × 10^4 caractères, cela représente 5 × 10^5 comparaisons, alors qu’un seul passage lirait chaque caractère une fois.

Algorithme

Définissez total = 0.
Prenez les dix lettres aeiouAEIOU une à la fois.
Pour chaque lettre, parcourez toute la chaîne et ajoutez 1 à total chaque fois qu’un caractère lui est égal.
Après les dix passages, renvoyez total.

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

Un passage avec une vérification des minuscules

Intuition

Inverse les boucles. Parcours la chaîne une fois et, pour chaque caractère, pose-toi une question : est-ce une voyelle ? Pour couvrir les deux cas avec une seule vérification, convertis d’abord le caractère en minuscule. I devient i et E devient e, tandis que les consonnes restent des consonnes ; tu n’as donc à comparer qu’aux cinq lettres a, e, i, o et u.

La vérification prend un temps constant : un switch sur cinq lettres, une recherche dans un ensemble ou une recherche dans la chaîne de cinq lettres aeiou. En parcourant Interview, le compteur augmente pour I, e, i et e, et se termine à 4.

Chaque caractère est lu une fois, donc le temps est de O(n). La mémoire se limite au compteur et aux cinq voyelles : espace O(1).

Algorithme

Définissez count = 0.
Parcourez la chaîne caractère par caractère.
Convertissez le caractère en minuscule.
S’il s’agit de a, e, i, o ou u, ajoutez 1 à count.
Retournez count.

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

Pièges et cas limites

La tâche tient en quelques lignes, et les erreurs viennent de cas oubliés par la première vérification.

Vérifier uniquement les minuscules. Comparer seulement avec aeiou ne détecte pas le I majuscule dans Interview et renvoie 3. Convertissez le caractère en minuscule ou énumérez les dix lettres.
Compter y. Dans ce problème, y n’est jamais une voyelle, donc rhythm donne 0.
Considérer l’index 0 comme une absence de correspondance. "aeiou".indexOf('a') vaut 0, ce qui signifie qu’il y a une correspondance. Testez si la valeur est -1 ou, en PHP, comparez strpos à false avec !==, car 0 == false dans ce langage.
Appeler strlen(s) dans la condition de boucle en C. La fonction parcourt toute la chaîne à chaque itération, donc 5 × 10^4 caractères coûtent environ 2.5 × 10^9 étapes. Arrêtez-vous au terminateur '\0' ou calculez la longueur une seule fois avant la boucle.

Questions fréquentes4

Comment compter les voyelles dans une chaîne de caractères ?

Parcourez la chaîne une seule fois avec un compteur. Convertissez chaque caractère en minuscule et vérifiez s’il s’agit de a, e, i, o ou u ; si c’est le cas, ajoutez 1. Lorsque la boucle se termine, le compteur contient la réponse.

Quelle est la complexité temporelle du comptage des voyelles ?

C’est O(n), où n est la longueur de la chaîne, car chaque caractère est vérifié une fois et chaque vérification compare au maximum cinq lettres. L’espace supplémentaire est O(1) : un compteur et l’ensemble fixe de voyelles.

Y est-il une voyelle dans ce problème ?

Non. En orthographe anglaise, y joue parfois le rôle d’une voyelle, comme dans rhythm, mais les problèmes de programmation définissent presque toujours les voyelles comme étant a, e, i, o et u, et c’est le cas ici. Si un problème inclut y, ajoute-le aux lettres que tu vérifies.

La vérification des voyelles doit-elle utiliser un ensemble, un switch ou une recherche dans une chaîne ?

Avec cinq lettres, les trois prennent un temps constant par caractère, et leur différence de vitesse est trop faible pour avoir de l’importance. Choisis celle qui se lit le mieux dans ton langage : un switch en C, C++ ou Go, un ensemble ou une recherche dans une chaîne en Python, JavaScript ou Ruby.

Python

def countVowels(s):
    # Écrivez le code ici

Cas de test

Cas 1

Cas 2

Entrée

s = "Interview"

Attendu