Les anagrammes, ou la clé canonique
Exercice · informatique (tronc commun des prépas scientifiques), chapitre 2 — Recherche séquentielle et dictionnaires
Énoncé
Écrire sont_anagrammes(u, v) testant si deux chaînes sont des anagrammes en complexité . Écrire ensuite groupes_anagrammes(mots) qui partitionne une liste de mots en groupes d'anagrammes.
Corrigé
def sont_anagrammes(u: str, v: str) -> bool:
# Deux mots sont des anagrammes s'ils ont le même dictionnaire de fréquences
return frequences(u) == frequences(v)
def groupes_anagrammes(mots: list) -> list:
groupes = {}
for m in mots:
# La clé canonique est le mot trié par ordre alphabétique
cle = "".join(sorted(m))
if cle not in groupes:
groupes[cle] = []
groupes[cle].append(m)
return list(groupes.values())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.