Premiers pas de dictionnaire

Exercice · informatique (tronc commun des prépas scientifiques), chapitre 2 — Recherche séquentielle et dictionnaires

Énoncé

Écrire une fonction frequences(s) renvoyant le dictionnaire d'occurrences des caractères de la chaîne s, puis l'utiliser pour identifier le caractère le plus fréquent de la chaîne "abracadabra".

Corrigé

def frequences(s: str) -> dict:
    f = {}
    for c in s:
        f[c] = f.get(c, 0) + 1
    return f

f = frequences("abracadabra")
# f vaut {'a': 5, 'b': 2, 'r': 2, 'c': 1, 'd': 1}

plus_frequent = None
for c in f:
    if plus_frequent is None or f[c] > f[plus_frequent]:
        plus_frequent = c
# plus_frequent vaut 'a'

Le comptage prend $O (n)$ étapes (où $n$ est le nombre de caractères). La recherche du maximum sur les clés du dictionnaire prend également $O (d)$ étapes (où $d \leq n$ est le nombre de caractères distincts). La complexité totale est linéaire, en $O (n)$ .

Les autres exercices de ce chapitre Le cours du chapitre

Un blocage sur cet exercice ? Le tuteur d'Adloun guide par questions, sans donner la réponse.