Count Vowels

Q: Qual è la complessità temporale del conteggio delle vocali?

È O(n) , dove n è la lunghezza della stringa, perché ogni carattere viene controllato una volta e ogni controllo lo confronta con al massimo cinque lettere. Lo spazio aggiuntivo è O(1) : un contatore e l'insieme fisso delle vocali.

Q: In questo problema, y è una vocale?

No. Nell'ortografia inglese, la y a volte funge da vocale, come in rhythm , ma i problemi di programmazione definiscono quasi sempre le vocali come a , e , i , o e u , e questo è uno di quelli. Se un problema include la y , aggiungila alle lettere che controlli.

PrincipianteArray e stringhe

+10

Ricevi una stringa s composta da lettere inglesi. Conta quanti dei suoi caratteri sono vocali e restituisci quel numero. Le vocali sono a, e, i, o e u, in minuscolo o maiuscolo. La lettera y non conta.

Funzione

countVowels(s: string) → integer

sstring: la stringa di lettere inglesi da analizzare
Restituisceinteger: il numero di vocali in s, sia maiuscole che minuscole

Vincoli

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

Esempi

Input: s = "Interview"
Output: 4
Spiegazione: Le vocali sono I, e, i ed e. La I maiuscola conta come una minuscola, quindi la risposta è 4.

Input: s = "rhythm"
Output: 0
Spiegazione: rhythm non contiene a, e, i, o né u. La sua y ha il suono di una vocale, ma non è nell’elenco, quindi la risposta è 0.

+18 test nascosti all’invio

Per approfondire

Riesci a restituire quante volte compare ciascuna delle cinque vocali, leggendo la stringa una sola volta?

Suggerimenti

Aprili uno alla volta. Ognuno rivela un po’ di più.

0 di 3 aperti

Soluzione

Il conteggio richiede un solo passaggio sulla stringa con un contatore. Le uniche decisioni riguardano come verificare se un carattere è una vocale e cosa fare con le lettere maiuscole. Converti ogni carattere in minuscolo e confrontalo con le cinque vocali: ogni carattere richiede una quantità costante di lavoro.

Conta ogni vocale con un passaggio dedicato

Intuizione

Suddividi la domanda in dieci domande più piccole: quante a ci sono, quante e e così via fino a U. Ognuna di queste è un semplice conteggio. Scorri la stringa e aggiungi 1 ogni volta che il carattere corrisponde alla lettera che stai cercando, poi somma i dieci conteggi.

Ogni vocale in s corrisponde esattamente a una delle dieci lettere in aeiouAEIOU, quindi viene conteggiata esattamente una volta, mentre nessuna consonante corrisponde a una di esse. Per Interview, il passaggio per e ne trova 2, quello per i ne trova 1, quello per I ne trova 1 e gli altri sette passaggi non trovano nulla: 4 in totale.

La stringa viene letta dieci volte, per circa 10n confronti. È comunque O(n), perché dieci è una costante, ma per 5 × 10^4 caratteri significa 5 × 10^5 confronti, mentre con un solo passaggio si leggerebbe ogni carattere una volta.

Algoritmo

Imposta total = 0.
Prendi le dieci lettere aeiouAEIOU una alla volta.
Per ogni lettera, percorri l'intera stringa e aggiungi 1 a total ogni volta che un carattere è uguale a essa.
Dopo i dieci passaggi, restituisci total.

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

Un passaggio con un controllo delle lettere minuscole

Intuizione

Inverti i cicli. Leggi la stringa una sola volta e, per ogni carattere, poniti una domanda: è una vocale? Per coprire entrambi i casi con un solo controllo, converti prima il carattere in minuscolo. I diventa i ed E diventa e, mentre le consonanti restano consonanti, quindi devi confrontare solo con le cinque lettere a, e, i, o e u.

Il controllo richiede un tempo costante: uno switch su cinque lettere, una ricerca in un insieme o una ricerca nella stringa di cinque lettere aeiou. Scorrendo Interview, il contatore aumenta in corrispondenza di I, e, i ed e e termina a 4.

Ogni carattere viene letto una sola volta, quindi il tempo è O(n). La memoria occupata dal contatore e dalle cinque vocali è O(1).

Algoritmo

Imposta count = 0.
Scorri la stringa un carattere alla volta.
Converti il carattere in minuscolo.
Se è a, e, i, o oppure u, aggiungi 1 a count.
Restituisci count.

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

Trappole e casi limite

Il compito si risolve in poche righe e gli errori derivano dai casi che il primo controllo dimentica.

Controllare solo le minuscole. Confrontare solo con aeiou non rileva la I maiuscola in Interview e restituisce 3. Converti il carattere in minuscolo oppure elenca tutte e dieci le lettere.
Contare y. In questo problema y non è mai una vocale, quindi rhythm dà 0.
Considerare l’indice 0 come un mancato riscontro. "aeiou".indexOf('a') è 0, che indica una corrispondenza. Verifica che il valore sia -1 oppure, in PHP, confronta strpos con false usando !==, perché in quel caso 0 == false.
Chiamare strlen(s) nella condizione del ciclo in C. Scorre l’intera stringa a ogni iterazione, quindi 5 × 10^4 caratteri richiedono circa 2.5 × 10^9 passaggi. Fermati al terminatore '\0' oppure calcola la lunghezza una volta prima del ciclo.

Domande frequenti4

Come si contano le vocali in una stringa?

Scorri la stringa una volta usando un contatore. Converti ogni carattere in minuscolo e controlla se è a, e, i, o oppure u; se lo è, aggiungi 1. Quando il ciclo termina, il contatore contiene la risposta.

Qual è la complessità temporale del conteggio delle vocali?

È O(n), dove n è la lunghezza della stringa, perché ogni carattere viene controllato una volta e ogni controllo lo confronta con al massimo cinque lettere. Lo spazio aggiuntivo è O(1): un contatore e l'insieme fisso delle vocali.

In questo problema, y è una vocale?

No. Nell'ortografia inglese, la y a volte funge da vocale, come in rhythm, ma i problemi di programmazione definiscono quasi sempre le vocali come a, e, i, o e u, e questo è uno di quelli. Se un problema include la y, aggiungila alle lettere che controlli.

Dovrebbe usare un insieme, uno <code>switch</code> o una ricerca nella stringa per verificare le vocali?

Con cinque lettere, tutte e tre richiedono un tempo costante per carattere e la differenza di velocità tra loro è troppo piccola per essere rilevante. Scegli quella che si legge meglio nel tuo linguaggio: uno switch in C, C++ o Go, un insieme o una ricerca in una stringa in Python, JavaScript o Ruby.

Python

def countVowels(s):
    # Scrivi il codice qui

Casi di test

Caso 1

Caso 2

Input

s = "Interview"

Atteso