Remove Vowels

Q: Como remover as vogais de uma string?

Percorra a string uma vez e copie cada letra que não seja a , e , i , o ou u (em qualquer uma das formas) para um construtor ou uma lista. Junte tudo em uma string no final. A ordem e a capitalização das letras mantidas permanecem como estavam.

Q: Qual é a complexidade de tempo para remover as vogais?

Uma passagem leva tempo O(n) , porque cada caractere passa por um teste de vogal em tempo constante. A saída ocupa espaço O(n) no pior caso, quando s não tem nenhuma vogal. Chamar replace uma vez por vogal também leva O(n) , mas lê a string dez vezes.

Q: Você consegue remover as vogais com uma expressão regular?

Sim. Substituir o padrão [aeiouAEIOU] por uma string vazia faz isso em uma única chamada na maioria das linguagens. A execução é O(n) , assim como o loop, mas os entrevistadores geralmente pedem que você escreva o loop para que possam ver o teste de vogais e como você monta o resultado.

InicianteArrays e strings

+10

Você recebe uma string s formada por letras do alfabeto inglês. Retorne a string obtida ao remover todas as vogais dela. As vogais são a, e, i, o e u, em letras minúsculas ou maiúsculas; y não é uma vogal aqui. As letras restantes mantêm sua ordem e suas maiúsculas ou minúsculas.

Função

removeVowels(s: string) → string

sstring: a string de letras em inglês a ser limpa
Retornastring: s com todas as vogais removidas e as outras letras em sua ordem original

Restrições

1 ≤ s.length ≤ 3 × 10⁴
s contém apenas letras do alfabeto inglês (a a z, A a Z).
s contém pelo menos uma letra que não é vogal, então a resposta nunca fica vazia.

Exemplos

Entrada: s = "Interview"
Saída: "ntrvw"
Explicação: Ao remover I, e, i e e de Interview, restam n, t, r, v, w, nessa ordem. O I maiúsculo também é uma vogal, então ele sai.

Entrada: s = "rhythm"
Saída: "rhythm"
Explicação: rhythm não tem a, e, i, o ou u, então nada é removido. O y não está na lista de vogais e permanece.

Entrada: s = "EuropeanUnion"
Saída: "rpnnn"
Explicação: Oito das treze letras de EuropeanUnion são vogais, incluindo as maiúsculas E e U. As cinco consoantes restantes, r, p, n, n, n, mantêm sua ordem e formam rpnnn.

+17 testes ocultos ao enviar

Para ir além

Que tal se o texto pudesse conter qualquer letra Unicode, como É ou ö? Quais delas são vogais, e como seu teste muda?

Dicas

Abra uma de cada vez. Cada uma revela um pouco mais.

0 de 3 abertas

Solução

Remover caracteres do meio de uma string é custoso se você fizer isso uma exclusão por vez, porque tudo depois do espaço se desloca. O melhor plano é montar a resposta: percorra a string uma vez e copie cada letra que não seja uma vogal. Os detalhes que você precisa acertar são as vogais maiúsculas e como o resultado é montado.

Exclua cada vogal em uma passada separada

Intuição

A maioria das linguagens pode excluir todas as ocorrências de um caractere de uma string em uma única chamada: substitua-o por nada. Faça isso dez vezes, uma para cada um de a e i o u A E I O U, e nenhuma vogal sobrará. As consoantes nunca são tocadas, então mantêm a ordem e a capitalização.

Para Interview, a passagem para e resulta em Intrviw, a passagem para i resulta em Intrvw, e a passagem para I resulta em ntrvw. As outras sete passagens não encontram nada para remover.

Cada passagem lê a string atual inteira, então o trabalho envolve cerca de 10n etapas de caracteres. Isso ainda é O(n), porque dez é uma constante, mas, para 3 × 10^4 letras, isso significa 3 × 10^5 etapas, enquanto uma única varredura precisa de 3 × 10^4.

Algoritmo

Pegue as dez letras de vogal aeiouAEIOU, uma de cada vez.
Para cada uma, substitua todas as ocorrências dela em s por nada.
Após as dez passagens, retorne o que restou de s.

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

Uma passagem que mantém as consoantes

Intuição

Inverta a tarefa: em vez de excluir as vogais, reúna todo o restante. Percorra s uma vez e, para cada caractere, verifique se ele é uma das dez letras que representam vogais. Se não for, acrescente-o ao resultado. Como você os acrescenta na ordem em que são lidos e nunca altera nenhum caractere, a ordem e as maiúsculas e minúsculas das consoantes permanecem exatamente como estavam.

Para EuropeanUnion, o percurso ignora E, u, o, e, a, U, i e o, e acrescenta r, p, n, n, n: o resultado é rpnnn.

Cada caractere requer um teste de tempo constante (uma consulta a um conjunto, um switch ou uma busca em uma string de dez letras), então o tempo é O(n). Reúna as letras em um construtor ou em uma lista e transforme-as em uma string uma única vez no final; aumentar uma string imutável com += faria com que ela fosse copiada a cada etapa. A própria saída ocupa espaço O(n).

Algoritmo

Inicie um construtor vazio para o resultado.
Percorra s um caractere por vez.
Se o caractere não for um dos aeiouAEIOU, adicione-o ao construtor.
Retorne o construtor como uma string.

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)

Armadilhas e casos extremos

A maioria das respostas incorretas ocorre por causa do teste de vogais ou da forma como a string de resultado cresce.

Esquecer as vogais maiúsculas. Testar apenas aeiou transforma Interview em Intrvw em vez de ntrvw. Verifique todas as dez letras ou converta o caractere para minúsculas antes do teste, mantendo o caractere original na saída.
Alterar a capitalização das letras mantidas. Se você converter a string inteira para minúsculas para simplificar o teste, QUEUEING retorna como qng em vez de QNG. Converta para minúsculas apenas a cópia usada no teste e acrescente o caractere original.
Excluir elementos ao percorrer a string para a frente por índice. Remover s[i] desloca a próxima letra para a posição i, e então i++ a pula, fazendo com que aab retorne como ab. Crie uma nova string ou percorra usando posições separadas de leitura e escrita.
Fazer uma string imutável crescer com += em um loop. Em Java ou C#, cada etapa copia a string inteira, cerca de 4.5 × 10^8 cópias de caracteres para 3 × 10^4 letras. Use um construtor de strings ou uma lista e concatene os elementos uma única vez.

Perguntas frequentes4

Como remover as vogais de uma string?

Percorra a string uma vez e copie cada letra que não seja a, e, i, o ou u (em qualquer uma das formas) para um construtor ou uma lista. Junte tudo em uma string no final. A ordem e a capitalização das letras mantidas permanecem como estavam.

Qual é a complexidade de tempo para remover as vogais?

Uma passagem leva tempo O(n), porque cada caractere passa por um teste de vogal em tempo constante. A saída ocupa espaço O(n) no pior caso, quando s não tem nenhuma vogal. Chamar replace uma vez por vogal também leva O(n), mas lê a string dez vezes.

Você consegue remover as vogais com uma expressão regular?

Sim. Substituir o padrão [aeiouAEIOU] por uma string vazia faz isso em uma única chamada na maioria das linguagens. A execução é O(n), assim como o loop, mas os entrevistadores geralmente pedem que você escreva o loop para que possam ver o teste de vogais e como você monta o resultado.

Por que não remover as vogais da string no próprio lugar?

Excluir um caractere do meio desloca todos os caracteres seguintes para a esquerda, então muitas exclusões podem custar O(n²). Você pode fazer isso no próprio lugar em O(n) usando dois índices: um que lê cada caractere e outro que escreve a próxima letra mantida. Porém, na maioria das linguagens, as strings não podem ser alteradas, então criar uma nova string é o caminho mais natural.

Python

def removeVowels(s):
    # Escreva o código aqui

Casos de teste

Caso 1

Caso 2

Caso 3

Entrada

s = "Interview"

Esperado

"ntrvw"