Count Vowels

Q: Qual é a complexidade de tempo da contagem de vogais?

É O(n) , em que n é o comprimento da string, porque cada caractere é verificado uma vez e cada verificação compara com no máximo cinco letras. O espaço extra é O(1) : um contador e o conjunto fixo de vogais.

Q: y é uma vogal neste problema?

Não. Na ortografia inglesa, y às vezes funciona como vogal, como em rhythm , mas problemas de programação quase sempre definem as vogais como a , e , i , o e u , e este problema faz isso. Se um problema incluir y , adicione-a às letras que você verifica.

InicianteArrays e strings

+10

Você recebe uma string s formada por letras do alfabeto inglês. Conte quantos de seus caracteres são vogais e retorne esse número. As vogais são a, e, i, o e u, em minúsculas ou maiúsculas. A letra y não conta.

Função

countVowels(s: string) → integer

sstring: o conjunto de letras em inglês a ser percorrido
Retornainteger: o número de vogais em s, maiúsculas e minúsculas juntas

Restrições

1 ≤ s.length ≤ 5 × 10⁴
s contém apenas letras do alfabeto inglês (a a z, A a Z).

Exemplos

Entrada: s = "Interview"
Saída: 4
Explicação: As vogais são I, e, i e e. A letra maiúscula I conta como uma minúscula, então a resposta é 4.

Entrada: s = "rhythm"
Saída: 0
Explicação: rhythm não tem a, e, i, o nem u. O y tem som de vogal, mas não está na lista, então a resposta é 0.

+18 testes ocultos ao enviar

Para ir além

Você consegue retornar quantas vezes cada uma das cinco vogais aparece, ainda lendo a string apenas uma vez?

Dicas

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

0 de 3 abertas

Solução

A contagem percorre a string uma vez usando um contador. As únicas decisões são como verificar se um caractere é uma vogal e o que fazer com letras maiúsculas. Converta cada caractere para minúscula e compare-o com as cinco vogais; cada caractere exige uma quantidade constante de trabalho.

Conte cada vogal em uma passagem própria

Intuição

Divida a pergunta em dez menores: quantos as há, quantos es, e assim por diante até U. Cada uma delas é uma contagem simples. Percorra a string e some 1 sempre que o caractere for igual à letra que você está procurando; depois, some as dez contagens.

Cada vogal em s é exatamente uma das dez letras em aeiouAEIOU, então é contada exatamente uma vez, e nenhuma consoante é igual a qualquer uma delas. Para Interview, a passagem para e encontra 2, a passagem para i encontra 1, a passagem para I encontra 1, e as outras sete passagens não encontram nada: 4 no total.

A string é lida dez vezes, o que dá cerca de 10n comparações. Isso ainda é O(n), porque dez é uma constante, mas, para 5 × 10^4 caracteres, significa 5 × 10^5 comparações, enquanto uma única passagem leria cada caractere uma vez.

Algoritmo

Defina total = 0.
Percorra as dez letras aeiouAEIOU uma de cada vez.
Para cada letra, percorra a string inteira e some 1 a total toda vez que um caractere for igual a ela.
Após as dez passagens, retorne total.

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

Uma passagem com uma verificação de letras minúsculas

Intuição

Inverta os loops. Leia a string uma vez e, para cada caractere, faça uma pergunta: é uma vogal? Para cobrir os dois casos com uma única verificação, converta primeiro o caractere para minúscula. I se torna i e E se torna e, enquanto as consoantes continuam sendo consoantes, então você só compara com as cinco letras a, e, i, o e u.

A verificação leva tempo constante: um switch com cinco letras, uma consulta em um conjunto ou uma busca na string de cinco letras aeiou. Percorrendo Interview, o contador aumenta em I, e, i e e, e termina em 4.

Cada caractere é lido uma vez, então o tempo é O(n). A memória é ocupada pelo contador e pelas cinco vogais: espaço O(1).

Algoritmo

Defina count = 0.
Percorra a string um caractere de cada vez.
Converta o caractere para minúsculas.
Se for a, e, i, o ou u, adicione 1 a count.
Retorne count.

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

Armadilhas e casos extremos

A tarefa cabe em poucas linhas, e os erros vêm de casos que a primeira verificação deixa passar.

Verificar apenas letras minúsculas. Comparar apenas com aeiou deixa passar o I maiúsculo em Interview e retorna 3. Converta o caractere para minúscula ou liste todas as dez letras.
Contar y. Neste problema, y nunca é uma vogal, então rhythm resulta em 0.
Tratar o índice 0 como uma falha. "aeiou".indexOf('a') é 0, o que significa que houve correspondência. Teste se o resultado é -1 ou, em PHP, compare strpos com false usando !==, porque lá 0 == false.
Chamar strlen(s) na condição do loop em C. Isso percorre toda a string em cada iteração, então 5 × 10^4 caracteres custam cerca de 2.5 × 10^9 etapas. Pare no terminador '\0' ou calcule o comprimento uma vez antes do loop.

Perguntas frequentes4

Como contar as vogais em uma string?

Percorra a string uma vez com um contador. Converta cada caractere para minúscula e verifique se ele é a, e, i, o ou u; se for, some 1. Quando o loop terminar, o contador conterá a resposta.

Qual é a complexidade de tempo da contagem de vogais?

É O(n), em que n é o comprimento da string, porque cada caractere é verificado uma vez e cada verificação compara com no máximo cinco letras. O espaço extra é O(1): um contador e o conjunto fixo de vogais.

y é uma vogal neste problema?

Não. Na ortografia inglesa, y às vezes funciona como vogal, como em rhythm, mas problemas de programação quase sempre definem as vogais como a, e, i, o e u, e este problema faz isso. Se um problema incluir y, adicione-a às letras que você verifica.

Verificar a vogal com um conjunto, um switch ou uma busca em uma string?

Com cinco letras, os três levam tempo constante por caractere, e a diferença de velocidade entre eles é pequena demais para importar. Escolha o que fica mais legível na sua linguagem: um switch em C, C++ ou Go, um conjunto ou uma busca em string em Python, JavaScript ou Ruby.

Python

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

Casos de teste

Caso 1

Caso 2

Entrada

s = "Interview"

Esperado