Count Vowels

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

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

Q: Est-ce que y est une voyelle dans ce problème ?

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

DébutantTableaux et chaînes

+10

Étant donné une chaîne s composée de lettres anglaises, renvoie le nombre de ses caractères qui sont des voyelles. 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 confondues

Contraintes

1 ≤ s.length ≤ 5 × 10⁴
s contient uniquement 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 une minuscule, donc la réponse est 4.

Entrée: s = "rhythm"
Sortie: 0
Explication: rhythm ne contient aucun a, e, i, o ni u, et y ne figure pas sur la liste, donc la réponse est 0.

Pour aller plus loin

Peux-tu renvoyer combien de fois chacune des cinq voyelles apparaît, en ne parcourant toujours 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

Parcourez la chaîne une seule fois à l’aide d’un compteur. Convertissez chaque caractère en minuscule, afin qu’une seule vérification des cinq voyelles couvre les deux casses.

Comptez chaque voyelle avec son propre passage

Intuition

Comptez chacune des dix lettres de aeiouAEIOU en parcourant la chaîne séparément, puis additionnez les dix comptes. Chaque voyelle correspond exactement à l’une des dix lettres : elle est donc comptée une fois, et aucune consonne ne correspond à l’une d’elles.

La chaîne est lue dix fois. Cela reste O(n), mais pour 5 × 10^4 caractères, cela représente 5 × 10^5 comparaisons, alors qu’un seul parcours lit chaque caractère une fois.

Algorithme

Définissez total = 0.
Prenez les dix lettres aeiouAEIOU une à une.
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

Parcourez la chaîne une fois et vérifiez pour chaque caractère s’il s’agit d’une voyelle. La convertir d’abord en minuscules transforme I en i et laisse les consonnes telles quelles : vous comparez ainsi avec cinq lettres au lieu de dix.

La vérification s’effectue en temps constant : avec un switch, une recherche dans un ensemble ou une recherche dans la chaîne aeiou. Chaque caractère est lu une seule fois et seul un compteur est stocké : O(n) en temps, O(1) en espace.

Algorithme

Définissez count = 0.
Parcourez la chaîne un caractère à la fois.
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

Ne vérifier que les minuscules. Comparer uniquement avec aeiou fait manquer le I majuscule dans Interview et renvoie 3.
Compter y. Ici, ce n’est jamais une voyelle, donc rhythm donne 0.
Traiter l’indice 0 comme une absence. "aeiou".indexOf('a') vaut 0, ce qui est une correspondance. Testez -1, ou en PHP comparez strpos à false avec !==, car 0 == false dans ce langage.
Appeler strlen(s) dans la condition de boucle en C. Cela reparcourt la chaîne à chaque étape, donc 5 × 10^4 caractères coûtent environ 2.5 × 10^9 étapes.

Questions fréquentes3

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

Parcourez la chaîne une seule fois à l’aide d’un compteur. Convertissez chaque caractère en minuscule et ajoutez 1 s’il s’agit de a, e, i, o ou u. Lorsque la boucle se termine, le compteur contient la réponse.

Quelle est la complexité temporelle du comptage des voyelles ?

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

Est-ce que y est une voyelle dans ce problème ?

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

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

Test #1

Test #2

Argument

s = "Interview"

Résultat attendu