Remove Vowels

Q: Come si rimuovono le vocali da una stringa?

Scorri la stringa una volta e copia ogni lettera che non è a , e , i , o o u (in maiuscolo o minuscolo) in un builder o in una lista. Alla fine, uniscile in una stringa. L’ordine e le maiuscole o minuscole delle lettere mantenute restano invariati.

Q: Qual è la complessità temporale della rimozione delle vocali?

Un pass richiede un tempo O(n) , perché ogni carattere viene sottoposto a un test della vocale in tempo costante. Nel caso peggiore, l'output occupa O(n) spazio, quando s non contiene alcuna vocale. Chiamare replace una volta per ogni vocale richiede anch'esso O(n) , ma legge la stringa dieci volte.

Q: Riesci a rimuovere le vocali con un'espressione regolare?

Sì. Sostituire il pattern [aeiouAEIOU] con una stringa vuota lo fa in una sola chiamata nella maggior parte dei linguaggi. Ha una complessità O(n) , come il ciclo, ma di solito chi conduce il colloquio ti chiede di scrivere il ciclo, così può vedere il controllo delle vocali e come costruisci il risultato.

PrincipianteArray e stringhe

+10

Hai una stringa s composta da lettere inglesi. Restituisci la stringa che ottieni eliminando tutte le vocali. Le vocali sono a, e, i, o e u, minuscole o maiuscole; qui y non è una vocale. Le lettere che rimangono mantengono il loro ordine e la loro forma.

Funzione

removeVowels(s: string) → string

sstring: la stringa di lettere inglesi da ripulire
Restituiscestring: s con ogni vocale rimossa e le altre lettere nel loro ordine originale

Vincoli

1 ≤ s.length ≤ 3 × 10⁴
s contiene solo lettere inglesi (a fino a z, A fino a Z).
s contiene almeno una lettera che non è una vocale, quindi la risposta non è mai vuota.

Esempi

Input: s = "Interview"
Output: "ntrvw"
Spiegazione: Eliminando I, e, i e e da Interview rimangono n, t, r, v, w in quest'ordine. Anche la I maiuscola è una vocale, quindi va eliminata.

Input: s = "rhythm"
Output: "rhythm"
Spiegazione: rhythm non contiene a, e, i, o né u, quindi non viene eliminato nulla. La sua y non è nell'elenco delle vocali e rimane.

Input: s = "EuropeanUnion"
Output: "rpnnn"
Spiegazione: Otto delle tredici lettere di EuropeanUnion sono vocali, incluse le maiuscole E e U. Le cinque consonanti rimanenti, r, p, n, n, n, mantengono il loro ordine e si leggono rpnnn.

+17 test nascosti all’invio

Per approfondire

Che cosa succederebbe se il testo potesse contenere qualsiasi lettera Unicode, come É o ö? Quali di queste sono vocali e in che modo cambia il tuo test?

Suggerimenti

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

0 di 3 aperti

Soluzione

Rimuovere caratteri dal centro di una stringa è costoso se lo fai una cancellazione alla volta, perché tutto ciò che si trova dopo il vuoto si sposta. Il piano migliore è invece costruire la risposta: percorri la stringa una volta e copia ogni lettera che non è una vocale. I dettagli da curare sono le vocali maiuscole e il modo in cui viene assemblato il risultato.

Elimina ogni vocale con la propria passata

Intuizione

La maggior parte dei linguaggi può eliminare in una sola chiamata ogni copia di un carattere da una stringa: sostituendolo con nulla. Fallo dieci volte, una per ciascuna di a e i o u A E I O U, e non resterà nessuna vocale. Le consonanti non vengono mai toccate, quindi mantengono il loro ordine e le maiuscole/minuscole.

Per Interview, il passaggio per e dà Intrviw, quello per i dà Intrvw e quello per I dà ntrvw. Gli altri sette passaggi non trovano nulla da rimuovere.

Ogni passaggio legge l'intera stringa corrente, quindi il lavoro richiede circa 10n passaggi sui caratteri. È comunque O(n), perché dieci è una costante, ma per 3 × 10^4 lettere significa 3 × 10^5 passaggi, mentre una singola scansione ne richiede 3 × 10^4.

Algoritmo

Prendi le dieci lettere vocali aeiouAEIOU una alla volta.
Per ognuna, sostituisci ogni sua occorrenza in s con niente.
Dopo i dieci passaggi, restituisci ciò che resta di s.

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

Un passaggio che mantiene le consonanti

Intuizione

Inverti il compito: invece di eliminare le vocali, raccogli tutto il resto. Scorri s una volta e, per ogni carattere, chiediti se è una delle dieci lettere vocaliche. Se non lo è, aggiungilo al risultato. Poiché aggiungi i caratteri nell’ordine in cui li leggi e non ne modifichi mai nessuno, l’ordine e le maiuscole o minuscole delle consonanti restano esattamente come nell’input.

Per EuropeanUnion, lo scorrimento salta E, u, o, e, a, U, i e o, e aggiunge r, p, n, n, n: il risultato è rpnnn.

Ogni carattere richiede un controllo a tempo costante (una ricerca in un insieme, un switch o una ricerca in una stringa di dieci lettere), quindi il tempo è O(n). Raccogli le lettere in un builder o in una lista e convertili in una stringa una sola volta alla fine; far crescere una stringa immutabile con += la copierebbe a ogni passaggio. L’output stesso occupa spazio O(n).

Algoritmo

Inizia un builder vuoto per il risultato.
Esamina s un carattere alla volta.
Se il carattere non è uno di aeiouAEIOU, aggiungilo al builder.
Restituisci il builder come stringa.

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)

Trappole e casi limite

La maggior parte delle risposte errate dipende dal test delle vocali o da come cresce la stringa risultato.

Dimenticare le vocali maiuscole. Controllare solo aeiou trasforma Interview in Intrvw invece che in ntrvw. Controlla tutte e dieci le lettere oppure converti il carattere in minuscolo prima del test, mantenendo il carattere originale nell'output.
Cambiare le maiuscole e minuscole delle lettere mantenute. Se converti l'intera stringa in minuscolo per rendere il test più breve, QUEUEING diventa qng invece di QNG. Converti in minuscolo solo la copia su cui esegui il test e aggiungi il carattere originale.
Eliminare elementi mentre si procede in avanti per indice. Rimuovendo s[i], la lettera successiva si sposta nella posizione i, e quindi i++ la salta: così aab diventa ab. Crea una nuova stringa oppure procedi usando posizioni separate per la lettura e la scrittura.
Far crescere una stringa immutabile con += in un ciclo. In Java o C#, ogni passaggio copia l'intera stringa: circa 4.5 × 10^8 copie di caratteri per 3 × 10^4 lettere. Usa un builder o una lista e uniscili una sola volta.

Domande frequenti4

Come si rimuovono le vocali da una stringa?

Scorri la stringa una volta e copia ogni lettera che non è a, e, i, o o u (in maiuscolo o minuscolo) in un builder o in una lista. Alla fine, uniscile in una stringa. L’ordine e le maiuscole o minuscole delle lettere mantenute restano invariati.

Qual è la complessità temporale della rimozione delle vocali?

Un pass richiede un tempo O(n), perché ogni carattere viene sottoposto a un test della vocale in tempo costante. Nel caso peggiore, l'output occupa O(n) spazio, quando s non contiene alcuna vocale. Chiamare replace una volta per ogni vocale richiede anch'esso O(n), ma legge la stringa dieci volte.

Riesci a rimuovere le vocali con un'espressione regolare?

Sì. Sostituire il pattern [aeiouAEIOU] con una stringa vuota lo fa in una sola chiamata nella maggior parte dei linguaggi. Ha una complessità O(n), come il ciclo, ma di solito chi conduce il colloquio ti chiede di scrivere il ciclo, così può vedere il controllo delle vocali e come costruisci il risultato.

Perché non eliminare le vocali dalla stringa direttamente?

Eliminare un carattere dal mezzo sposta a sinistra ogni carattere successivo, quindi molte eliminazioni possono costare O(n²). Puoi farlo sul posto in O(n) con due indici: uno legge ogni carattere e l’altro scrive il carattere successivo da mantenere, ma nella maggior parte dei linguaggi le stringhe non possono essere modificate, quindi creare una nuova stringa è la soluzione più naturale.

Python

def removeVowels(s):
    # Scrivi il codice qui

Casi di test

Caso 1

Caso 2

Caso 3

Input

s = "Interview"

Atteso

"ntrvw"