Count a Character

Q: Posso usar uma função de contagem integrada em uma entrevista?

Geralmente sim, desde que você saiba dizer qual é o custo. str.count do Python e funções semelhantes ainda leem a string inteira, então são O(n) . Esteja preparado para escrever o loop se o entrevistador pedir.

InicianteArrays e strings

+10

Você recebe uma string s e uma única letra c. Retorne quantas vezes c aparece em s. A correspondência diferencia maiúsculas de minúsculas: B e b são caracteres diferentes.

Função

countChar(s: string, c: string) → integer

sstring: a sequência de letras em inglês a ser pesquisada
cstring: a letra que deve ser contada
Retornainteger: quantos caracteres de s são iguais a c

Restrições

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

Exemplos

Entrada: s = "Mississippi"c = "s"
Saída: 4
Explicação: Mississippi tem um s nos índices 2, 3, 5 e 6, então a resposta é 4.

Entrada: s = "Banana"c = "b"
Saída: 0
Explicação: Banana começa com um B maiúsculo, e você está procurando um b minúsculo. Nada corresponde, então a resposta é 0.

Para ir além

E se c pudesse ser uma palavra com várias letras, como ss? Correspondências sobrepostas contam, e como seu loop muda?

Dicas

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

0 de 3 abertas

Solução

Qualquer caractere de s pode ser um c, então você verifica cada um uma vez e conta as correspondências. Atenção às maiúsculas e minúsculas: uma letra maiúscula é um caractere diferente.

Exclua todos os c e compare os comprimentos

Intuição

Crie uma cópia de s removendo cada c. Cada remoção deixa a cópia um caractere menor, então a diferença de comprimento é a contagem. Para Mississippi, a cópia é Miiippi: 11 menos 7 é 4.

O tempo é O(n), mas a cópia usa O(n) de memória extra que um contador não precisa.

Algoritmo

Faça uma cópia de s que omita todos os caracteres iguais a c.
Meça o comprimento de s e o comprimento da cópia.
Retorne o comprimento de s menos o comprimento da cópia.

def countChar(s, c):
    # Every c that disappears makes the string one character shorter.
    without = s.replace(c, "")
    return len(s) - len(without)

Uma passagem com um contador

Intuição

Conte enquanto lê, em vez de criar uma cópia. Um contador começa em 0 e aumenta em 1 para cada caractere igual a c. A igualdade simples impede que uma letra maiúscula corresponda a uma minúscula.

Cada caractere é comparado uma única vez e apenas o contador é armazenado: tempo O(n), espaço O(1). Nenhuma solução supera o tempo O(n), porque um caractere ignorado poderia ser mais um c.

Algoritmo

Leia a letra-alvo de c e defina count = 0.
Percorra s um caractere por vez.
Se o caractere for igual ao alvo, adicione 1 a count.
Retorne count.

def countChar(s, c):
    count = 0
    for ch in s:
        if ch == c:
            count += 1
    return count

Armadilhas e casos extremos

Ignorar maiúsculas e minúsculas. Converter ambos os lados para minúsculas faz com que Banana com b retorne 1; a resposta é 0.
Comparar um caractere com uma string. Em Java, C, C++, C# e Go, c chega como uma string, enquanto s[i] ou s.charAt(i) é um caractere. Pegue c[0] (ou c.charAt(0)) uma vez antes do loop.
Comparar strings com == em Java. String.valueOf(s.charAt(i)) == c compara a identidade dos objetos e quase sempre é falso. Compare valores do tipo char.
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 ocorrências de um caractere em uma string?

Percorra a string uma vez com um contador que começa em 0 e some 1 cada vez que o caractere atual for igual ao que você quer. Isso leva O(n) de tempo e O(1) de memória extra. Para contar sem diferenciar maiúsculas de minúsculas, primeiro converta a string e a letra para minúsculas.

Posso usar uma função de contagem integrada em uma entrevista?

Geralmente sim, desde que você saiba dizer qual é o custo. str.count do Python e funções semelhantes ainda leem a string inteira, então são O(n). Esteja preparado para escrever o loop se o entrevistador pedir.

Como você contaria todos os caracteres de uma só vez?

Faça uma única passada e mantenha uma contagem por caractere, em um mapa hash ou em um array de 52 contadores para as letras do inglês. Depois dessa passada, a contagem de qualquer letra é uma única consulta. Use isso quando perguntarem sobre várias letras na mesma string.

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

Teste #1

Teste #2

Argumentos

s = "Mississippi"
c = "s"

Saída Esperada