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 rispetto a un massimo di cinque lettere. Lo spazio aggiuntivo è O(1) : un contatore e l'insieme fisso delle vocali.

Q: In questo problema, y è una vocale?

No. Nella grafia inglese y a volte funge da vocale, come in rhythm , ma nei problemi di programmazione le vocali sono quasi sempre definite come a , e , i , o e u , e questo problema fa così. Se un problema include y , aggiungila alle lettere che controlli.

PrincipianteArray e stringhe

+10

Data una stringa s composta da lettere inglesi, restituisci il numero dei suoi caratteri che sono vocali. Le vocali sono a, e, i, o e u, sia minuscole che maiuscole. 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, tra maiuscole e 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, e y non è nell’elenco, quindi la risposta è 0.

Per approfondire

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

Suggerimenti

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

0 di 3 aperti

Soluzione

Leggi la stringa una volta usando un contatore. Converti ogni carattere in minuscolo, così un solo controllo rispetto alle cinque vocali copre entrambe le maiuscole e le minuscole.

Conta ogni vocale con un passaggio dedicato

Intuizione

Conta ciascuna delle dieci lettere in aeiouAEIOU con una propria scansione della stringa, poi somma i dieci conteggi. Ogni vocale corrisponde esattamente a una delle dieci lettere, quindi viene contata una volta, e nessuna consonante corrisponde a una di esse.

La stringa viene letta dieci volte. È comunque O(n), ma per 5 × 10^4 caratteri significa 5 × 10^5 confronti, mentre una scansione legge ogni carattere una volta.

Algoritmo

Imposta total = 0.
Prendi le dieci lettere aeiouAEIOU una alla volta.
Per ogni lettera, percorri tutta la 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

Leggi la stringa una volta e chiediti, per ogni carattere, se è una vocale. Convertirla prima in minuscolo trasforma I in i e lascia le consonanti invariate, così confronti cinque lettere invece di dieci.

Il controllo richiede tempo costante: un switch, una ricerca in un insieme o una ricerca nella stringa aeiou. Ogni carattere viene letto una volta e viene memorizzato solo un contatore: tempo O(n), spazio O(1).

Algoritmo

Imposta count = 0.
Esamina 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

Controllare solo le lettere minuscole. Confrontare solo con aeiou non rileva la I maiuscola in Interview e restituisce 3.
Contare y. Qui non è mai una vocale, quindi rhythm restituisce 0.
Considerare l'indice 0 come una mancata corrispondenza. "aeiou".indexOf('a') è 0, quindi è una corrispondenza. Verifica che sia -1 oppure, in PHP, confronta strpos con false usando !==, perché lì 0 == false.
Chiamare strlen(s) nella condizione del ciclo in C. La stringa viene scandita di nuovo a ogni passaggio, quindi 5 × 10^4 caratteri richiedono circa 2.5 × 10^9 passaggi.

Domande frequenti3

Come si contano le vocali in una stringa?

Esamina la stringa una volta usando un contatore. Converti ogni carattere in minuscolo e aggiungi 1 se è a, e, i, o o u. 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 rispetto a un massimo di cinque lettere. Lo spazio aggiuntivo è O(1): un contatore e l'insieme fisso delle vocali.

In questo problema, y è una vocale?

No. Nella grafia inglese y a volte funge da vocale, come in rhythm, ma nei problemi di programmazione le vocali sono quasi sempre definite come a, e, i, o e u, e questo problema fa così. Se un problema include y, aggiungila alle lettere che controlli.

def countVowels(s):
    # Scrivi il codice qui

Test #1

Test #2

Argomento

s = "Interview"

Output atteso