Count a Character

Q: Puis-je utiliser une fonction intégrée de comptage lors d’un entretien ?

En général, oui, tant que tu peux expliquer son coût. str.count et les fonctions similaires de Python parcourent quand même toute la chaîne, donc leur complexité est O(n) . Prépare-toi à écrire la boucle si la personne qui te fait passer l’entretien te le demande.

DébutantTableaux et chaînes

+10

Vous recevez une chaîne s et une lettre unique c. Retournez le nombre de fois où c apparaît dans s. La correspondance respecte la casse : B et b sont des caractères différents.

Fonction

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

sstring: la chaîne de lettres anglaises à rechercher
cstring: l’unique lettre à compter
Renvoieinteger: combien de caractères de s sont égaux à c

Contraintes

1 ≤ s.length ≤ 5 × 10⁴
s ne contient que des lettres anglaises (a à z, A à Z).
c est exactement une lettre anglaise.

Exemples

Entrée: s = "Mississippi"c = "s"
Sortie: 4
Explication: Mississippi contient un s aux indices 2, 3, 5 et 6, donc la réponse est 4.

Entrée: s = "Banana"c = "b"
Sortie: 0
Explication: Banana commence par une majuscule B, et tu cherches un petit b. Rien ne correspond, donc la réponse est 0.

Pour aller plus loin

Et si c pouvait être un mot de plusieurs lettres, comme ss ? Les correspondances qui se chevauchent sont-elles comptabilisées, et comment ta boucle change-t-elle ?

Indices

Ouvrez-les un par un. Chacun en dévoile un peu plus.

0 sur 3 ouverts

Solution

N’importe quel caractère de s peut être un c, alors examine chaque caractère une fois et compte les correspondances. Attention à la casse : une majuscule est un caractère différent.

Supprimez chaque c et comparez les longueurs

Intuition

Créez une copie de s dans laquelle chaque c est supprimé. Chaque suppression raccourcit la copie d’un caractère, donc la différence de longueur correspond au nombre de suppressions. Pour Mississippi, la copie est Miiippi : 11 moins 7 égale 4.

La complexité temporelle est de O(n), mais la copie nécessite O(n) de mémoire supplémentaire dont un compteur n’a pas besoin.

Algorithme

Fais une copie de s en omettant chaque caractère égal à c.
Mesure la longueur de s et celle de la copie.
Retourne la longueur de s moins la longueur de la copie.

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

Un passage avec un compteur

Intuition

Comptez au fur et à mesure de la lecture au lieu de créer une copie. Un compteur commence à 0 et augmente de 1 pour chaque caractère égal à c. Une simple égalité empêche une lettre majuscule de correspondre à une minuscule.

Chaque caractère est comparé une seule fois et seul le compteur est stocké : O(n) en temps, O(1) en espace. Aucune solution ne fait mieux que O(n) en temps, car un caractère ignoré pourrait être un c supplémentaire.

Algorithme

Lire la lettre cible à partir de c et définir count = 0.
Parcourir s un caractère à la fois.
Si le caractère est égal à la cible, ajouter 1 à count.
Retourner count.

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

Pièges et cas limites

Ignorer la casse. Mettre les deux côtés en minuscules fait que Banana avec b renvoie 1 ; la réponse est 0.
Comparer un caractère avec une chaîne. En Java, C, C++, C# et Go, c est une chaîne tandis que s[i] ou s.charAt(i) est un seul caractère. Prenez c[0] (ou c.charAt(0)) une seule fois avant la boucle.
Comparer des chaînes avec == en Java. String.valueOf(s.charAt(i)) == c compare l’identité des objets et est presque toujours faux. Comparez des valeurs de type char.
Appeler strlen(s) dans la condition de boucle en C. Cela parcourt à nouveau la chaîne à chaque étape, donc 5 × 10^4 caractères coûtent environ 2.5 × 10^9 étapes.

Questions fréquentes3

Comment compter les occurrences d’un caractère dans une chaîne de caractères ?

Parcours la chaîne une fois avec un compteur qui commence à 0, et ajoute 1 chaque fois que le caractère courant est égal à celui que tu cherches. Cela prend O(n) de temps et O(1) de mémoire supplémentaire. Pour compter sans tenir compte de la casse, convertis d’abord la chaîne et la lettre en minuscules.

Puis-je utiliser une fonction intégrée de comptage lors d’un entretien ?

En général, oui, tant que tu peux expliquer son coût. str.count et les fonctions similaires de Python parcourent quand même toute la chaîne, donc leur complexité est O(n). Prépare-toi à écrire la boucle si la personne qui te fait passer l’entretien te le demande.

Comment compter tous les caractères en une seule fois ?

Effectuez un seul parcours et comptabilisez chaque caractère dans une table de hachage ou dans un tableau de 52 compteurs pour les lettres anglaises. Après ce parcours, le nombre d’occurrences de n’importe quelle lettre s’obtient en une seule recherche. Utilisez cette méthode lorsqu’on vous interroge sur plusieurs lettres dans la même chaîne.

def countChar(s, c):
    # Écrivez le code ici

Test #1

Test #2

Arguments

s = "Mississippi"
c = "s"

Résultat attendu