Familles d'anagrammes — exercice corrigé de programmation Java (école d'ingénieur) (chapitre 12)

Familles d'anagrammes

Collections et génériques · niveau 3 (difficile)

Énoncé

Deux mots sont des anagrammes s'ils s'écrivent avec les mêmes lettres : chien, niche et chine. Écrire un programme qui, à partir du tableau {"chien", "niche", "marie", "aimer", "chine", "ramie", "loup", "poule"}, affiche les familles d'au moins deux anagrammes. Indication : deux mots sont anagrammes si et seulement si leurs lettres, triées, forment la même chaîne ; utiliser cette chaîne comme clé d'un dictionnaire.

Corrigé

La signature d'un mot est la chaîne de ses lettres triées : chien, niche et chine ont la même, cehin. Le dictionnaire associe à chaque signature la liste des mots qui l'ont.


import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Map;
import java.util.TreeMap;

public class Exo7Anagrammes {
    static String signature(String mot) {
        char[] t = mot.toCharArray();
        Arrays.sort(t);
        return new String(t);
    }
    public static void main(String[] args) {
        String[] mots = {"chien", "niche", "marie", "aimer", "chine", "ramie", "loup", "poule"};
        Map<String, List<String>> groupes = new TreeMap<>();
        for (String m : mots) {
            String cle = signature(m);
            if (!groupes.containsKey(cle)) groupes.put(cle, new ArrayList<>());
            groupes.get(cle).add(m);
        }
        for (List<String> g : groupes.values()) {
            if (g.size() > 1) System.out.println(g);
        }
    }
}


[marie, aimer, ramie]
[chien, niche, chine]

La ligne groupes.get(cle).add(m) modifie la liste rangée dans le dictionnaire : get renvoie une référence vers cette liste, pas une copie. Les groupes sortent dans l'ordre des signatures (aeimr avant cehin). loup et poule restent seuls : poule a un e de plus.