informatique (tronc commun des prépas scientifiques) · Chapitre 2 · Exercice de TD
Les anagrammes, ou la clé canonique
Recherche séquentielle et dictionnaires · niveau 3 (difficile)
É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())