Remove Vowels

Q: Quelle est la complexité temporelle de la suppression des voyelles ?

Un seul parcours prend un temps de O(n) , car chaque caractère fait l’objet d’un test constant de voyelle. La sortie nécessite un espace de O(n) dans le pire des cas, lorsque s ne contient aucune voyelle. Appeler replace une fois par voyelle est également en O(n) , mais cela lit la chaîne dix fois.

Q: Peux-tu supprimer les voyelles à l’aide d’une expression régulière ?

Oui. Remplacer le motif [aeiouAEIOU] par une chaîne vide permet de le faire en un seul appel dans la plupart des langages. Cela s’exécute en O(n) , comme la boucle, mais les recruteurs vous demandent généralement d’écrire la boucle afin de voir le test des voyelles et la façon dont vous construisez le résultat.

DébutantTableaux et chaînes

+10

Vous recevez une chaîne s composée de lettres anglaises. Renvoyez la chaîne obtenue en supprimant toutes les voyelles. Les voyelles sont a, e, i, o et u, en minuscules ou en majuscules ; y n’est pas une voyelle ici. Les lettres conservées gardent leur ordre et leur casse.

Fonction

removeVowels(s: string) → string

sstring: la chaîne de lettres anglaises à nettoyer
Renvoiestring: s avec toutes les voyelles supprimées et les autres lettres dans leur ordre d’origine

Contraintes

1 ≤ s.length ≤ 3 × 10⁴
s contient uniquement des lettres anglaises (a à z, A à Z).
s contient au moins une lettre qui n’est pas une voyelle, donc la réponse n’est jamais vide.

Exemples

Entrée: s = "Interview"
Sortie: "ntrvw"
Explication: En supprimant I, e, i et e de Interview, il reste n, t, r, v, w dans cet ordre. Le I majuscule est aussi une voyelle, alors on le supprime.

Entrée: s = "rhythm"
Sortie: "rhythm"
Explication: rhythm ne contient pas de a, de e, de i, de o ni de u, donc rien n’est supprimé. Son y ne figure pas dans la liste des voyelles et reste.

Entrée: s = "EuropeanUnion"
Sortie: "rpnnn"
Explication: Huit des treize lettres de EuropeanUnion sont des voyelles, y compris les majuscules E et U. Les cinq consonnes restantes, r, p, n, n, n, conservent leur ordre et forment rpnnn.

+17 tests cachés à la soumission

Pour aller plus loin

Et si le texte pouvait contenir n’importe quelle lettre Unicode, comme É ou ö ? Lesquelles sont des voyelles, et comment ton test change-t-il ?

Indices

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

0 sur 3 ouverts

Solution

Supprimer des caractères au milieu d’une chaîne coûte cher si tu le fais une suppression à la fois, car tout ce qui se trouve après l’espace se décale. La meilleure approche consiste plutôt à construire le résultat : parcours la chaîne une fois et copie chaque lettre qui n’est pas une voyelle. Il faut notamment bien gérer les voyelles majuscules et assembler le résultat.

Supprime chaque voyelle en un passage distinct

Intuition

La plupart des langages peuvent supprimer toutes les occurrences d’un caractère d’une chaîne en un seul appel : en le remplaçant par rien. Fais cela dix fois, une fois pour chacun des caractères a e i o u A E I O U, et il ne restera aucune voyelle. Les consonnes ne sont jamais touchées, elles gardent donc leur ordre et leur casse.

Pour Interview, le passage pour e donne Intrviw, celui pour i donne Intrvw, et celui pour I donne ntrvw. Les sept autres passages ne trouvent rien à supprimer.

Chaque passage lit toute la chaîne actuelle, le travail représente donc environ 10n étapes de caractère. Cela reste O(n), car dix est une constante, mais pour 3 × 10^4 lettres, cela représente 3 × 10^5 étapes, alors qu’un seul parcours en nécessite 3 × 10^4.

Algorithme

Parcourez les dix lettres voyelles aeiouAEIOU une par une.
Pour chacune, remplacez chaque occurrence dans s par rien.
Après les dix passes, renvoyez ce qui reste de s.

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

Un passage qui conserve les consonnes

Intuition

Inverse la tâche : au lieu de supprimer les voyelles, collecte tout le reste. Parcours s une fois et, pour chaque caractère, vérifie s’il s’agit de l’une des dix lettres voyelles. Si ce n’est pas le cas, ajoute-le au résultat. Comme tu ajoutes les caractères dans l’ordre de lecture et que tu n’en modifies jamais aucun, l’ordre et la casse des consonnes restent exactement tels qu’ils étaient à l’origine.

Pour EuropeanUnion, le parcours ignore E, u, o, e, a, U, i et o, et ajoute r, p, n, n, n : le résultat est rpnnn.

Chaque caractère nécessite un test en temps constant (une recherche dans un ensemble, un switch ou une recherche dans une chaîne de dix lettres), donc le temps d’exécution est de O(n). Collecte les lettres dans un constructeur de chaîne ou une liste, puis transforme-les en chaîne une seule fois à la fin ; agrandir une chaîne immuable avec += en copierait le contenu à chaque étape. La sortie elle-même constitue l’espace O(n).

Algorithme

Commencez par un constructeur vide pour le résultat.
Parcourez s caractère par caractère.
Si le caractère n’est pas l’un de aeiouAEIOU, ajoutez-le au constructeur.
Renvoyez le constructeur sous forme de chaîne.

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)

Pièges et cas limites

La plupart des mauvaises réponses viennent du test des voyelles ou de la façon dont la chaîne de résultat s’allonge.

Oublier les voyelles majuscules. Tester uniquement aeiou transforme Interview en Intrvw au lieu de ntrvw. Vérifie les dix lettres, ou convertis le caractère en minuscules avant le test, et conserve le caractère d’origine dans le résultat.
Modifier la casse des lettres conservées. Si tu convertis toute la chaîne en minuscules pour simplifier le test, QUEUEING devient qng au lieu de QNG. Convertis uniquement la copie que tu testes en minuscules, et ajoute le caractère d’origine.
Supprimer des caractères en parcourant la chaîne vers l’avant par indice. Supprimer s[i] décale la lettre suivante à la position i, puis i++ la saute, si bien que aab devient ab. Construis une nouvelle chaîne, ou parcours-la avec des positions de lecture et d’écriture distinctes.
Allonger une chaîne immuable avec += dans une boucle. En Java ou en C#, chaque étape copie toute la chaîne, soit environ 4.5 × 10^8 copies de caractères pour 3 × 10^4 lettres. Utilise un constructeur de chaîne ou une liste, puis assemble-les une seule fois.

Questions fréquentes4

Comment supprimer les voyelles d’une chaîne de caractères ?

Parcourez la chaîne une seule fois et copiez chaque lettre qui n’est ni a, e, i, o ni u (quelle que soit sa casse) dans un générateur ou une liste. À la fin, assemblez le tout en une chaîne. L’ordre et la casse des lettres conservées restent inchangés.

Quelle est la complexité temporelle de la suppression des voyelles ?

Un seul parcours prend un temps de O(n), car chaque caractère fait l’objet d’un test constant de voyelle. La sortie nécessite un espace de O(n) dans le pire des cas, lorsque s ne contient aucune voyelle. Appeler replace une fois par voyelle est également en O(n), mais cela lit la chaîne dix fois.

Peux-tu supprimer les voyelles à l’aide d’une expression régulière ?

Oui. Remplacer le motif [aeiouAEIOU] par une chaîne vide permet de le faire en un seul appel dans la plupart des langages. Cela s’exécute en O(n), comme la boucle, mais les recruteurs vous demandent généralement d’écrire la boucle afin de voir le test des voyelles et la façon dont vous construisez le résultat.

Pourquoi ne pas supprimer les voyelles de la chaîne directement ?

Supprimer un caractère au milieu décale vers la gauche tous les caractères suivants, si bien que de nombreuses suppressions peuvent coûter O(n²). Vous pouvez le faire en place en O(n) à l’aide de deux index : l’un qui lit chaque caractère et l’autre qui écrit la prochaine lettre conservée. Cependant, dans la plupart des langages, les chaînes ne peuvent pas être modifiées, donc construire une nouvelle chaîne est la solution la plus naturelle.

Python

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

Cas de test

Cas 1

Cas 2

Cas 3

Entrée

s = "Interview"

Attendu

"ntrvw"