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 em relação a 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 os problemas de programação quase sempre definem as vogais como a , e , i , o e u , e este é um deles. Se um problema incluir y , adicione-o às letras que você verifica.

InicianteArrays e strings

+10

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

Função

countVowels(s: string) → integer

sstring: a sequência de letras em inglês a ser examinada
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. O I maiúsculo conta como uma letra 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, e y não está na lista, então a resposta é 0.

Para ir além

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

Dicas

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

0 de 3 abertas

Solução

Leia a string uma vez usando um contador. Converta cada caractere para minúsculas, assim uma verificação das cinco vogais abrange ambos os casos.

Conte cada vogal em uma passagem separada

Intuição

Conte cada uma das dez letras em aeiouAEIOU com uma passagem própria pela string e, em seguida, some as dez contagens. Cada vogal corresponde exatamente a uma das dez letras, então é contada uma vez, e nenhuma consoante corresponde a nenhuma delas.

A string é lida dez vezes. Isso ainda é O(n), mas, para 5 × 10^4 caracteres, isso significa 5 × 10^5 comparações, enquanto uma passagem lê cada caractere uma vez.

Algoritmo

Defina total = 0.
Pegue as dez letras aeiouAEIOU uma de cada vez.
Para cada letra, percorra a string inteira e adicione 1 a total sempre 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

Leia a string uma vez e verifique se cada caractere é uma vogal. Convertê-la para minúsculas primeiro transforma I em i e mantém as consoantes como consoantes, então você compara com cinco letras em vez de dez.

A verificação leva tempo constante: um switch, uma busca em um conjunto ou uma busca na string aeiou. Cada caractere é lido uma vez e apenas um contador é armazenado: tempo O(n), espaço O(1).

Algoritmo

Defina count = 0.
Percorra a string um caractere por 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

Verificar apenas letras minúsculas. Comparar apenas com aeiou não detecta o I maiúsculo em Interview e retorna 3.
Contar y. Aqui, ela nunca é uma vogal, então rhythm resulta em 0.
Tratar o índice 0 como uma ausência. "aeiou".indexOf('a') é 0, o que significa que houve uma correspondência. Teste se o valor é -1 ou, em PHP, compare strpos com false usando !==, porque em PHP 0 == false.
Chamar strlen(s) na condição do loop em C. Isso percorre a string novamente a cada etapa, então 5 × 10^4 caracteres custam cerca de 2.5 × 10^9 etapas.

Perguntas frequentes3

Como contar as vogais em uma string?

Percorra a string uma vez usando um contador. Converta cada caractere para minúsculas e adicione 1 se ele for a, e, i, o ou u. 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 em relação a 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 os problemas de programação quase sempre definem as vogais como a, e, i, o e u, e este é um deles. Se um problema incluir y, adicione-o às letras que você verifica.

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

Teste #1

Teste #2

Argumento

s = "Interview"

Saída Esperada