Le problème Word Ladder consiste à transformer un mot de départ en un mot d'arrivée en changeant une seule lettre à la fois, chaque étape intermédiaire devant figurer dans un dictionnaire donné. Il s'agit d'un problème classique de théorie des graphes qui peut être modélisé comme la recherche du plus court chemin dans un graphe non pondéré.

Word Ladder : Trouver la longueur du plus court chemin

Pour déterminer la longueur minimale de la séquence de transformation, l'algorithme de recherche en largeur (BFS - Breadth-First Search) est l'approche la plus efficace. Le BFS garantit que le premier chemin atteignant la cible est le plus court.

public int calculerLongueurEchelle(String debut, String cible, Set<String> dictionnaire) {
    if (!dictionnaire.contains(cible)) return 0;

    Queue<String> fileAttente = new LinkedList<>();
    fileAttente.offer(debut);
    
    Set<String> visite = new HashSet<>();
    visite.add(debut);
    
    int niveau = 1;

    while (!fileAttente.isEmpty()) {
        int tailleNiveau = fileAttente.size();
        for (int i = 0; i < tailleNiveau; i++) {
            String motActuel = fileAttente.poll();
            
            if (motActuel.equals(cible)) return niveau;
            
            char[] caracteres = motActuel.toCharArray();
            for (int j = 0; j < caracteres.length; j++) {
                char original = caracteres[j];
                for (char c = 'a'; c <= 'z'; c++) {
                    if (c == original) continue;
                    caracteres[j] = c;
                    String nouveauMot = String.valueOf(caracteres);
                    
                    if (nouveauMot.equals(cible)) return niveau + 1;
                    
                    if (dictionnaire.contains(nouveauMot) && !visite.contains(nouveauMot)) {
                        visite.add(nouveauMot);
                        fileAttente.offer(nouveauMot);
                    }
                }
                caracteres[j] = original;
            }
        }
        niveau++;
    }
    return 0;
}

Word Ladder II : Extraction de tous les chemins optimaux

Contrairement au premier problème, Word Ladder II exige de retourner toutes les séquences de transformation de longueur minimale. Pour y parvenir, nous utilisons une stratégie en deux étapes :

1. BFS : Pour construire un dictionnaire de distances (ou un graphe de niveaux) qui enregistre la distance minimale de chaque mot par rapport au point de départ.
2. DFS (Backtracking) : Pour reconstruire tous les chemins possibles en remontant du mot cible vers le mot de départ, en s'assurant que chaque étape réduit la distance d'exactement une unité.

public class WordLadderSolver {
    private Map<String, Integer> carteDistances = new HashMap<>();
    private List<List<String>> resultats = new ArrayList<>();

    public List<List<String>> trouverEchelles(String debut, String fin, Set<String> dico) {
        dico.add(fin);
        genererDistances(debut, dico);
        
        if (carteDistances.containsKey(fin)) {
            backtrack(fin, debut, new LinkedList<>(Arrays.asList(fin)));
        }
        return resultats;
    }

    private void genererDistances(String debut, Set<String> dico) {
        Queue<String> queue = new LinkedList<>();
        queue.add(debut);
        carteDistances.put(debut, 0);

        while (!queue.isEmpty()) {
            String mot = queue.poll();
            int dist = carteDistances.get(mot);
            
            char[] lettres = mot.toCharArray();
            for (int i = 0; i < lettres.length; i++) {
                char temp = lettres[i];
                for (char c = 'a'; c <= 'z'; c++) {
                    lettres[i] = c;
                    String voisin = String.valueOf(lettres);
                    if (dico.contains(voisin) && !carteDistances.containsKey(voisin)) {
                        carteDistances.put(voisin, dist + 1);
                        queue.add(voisin);
                    }
                }
                lettres[i] = temp;
            }
        }
    }

    private void backtrack(String courant, String cible, LinkedList<String> chemin) {
        if (courant.equals(cible)) {
            List<String> copie = new ArrayList<>(chemin);
            Collections.reverse(copie);
            resultats.add(copie);
            return;
        }

        int distCible = carteDistances.get(courant);
        char[] lettres = courant.toCharArray();
        for (int i = 0; i < lettres.length; i++) {
            char temp = lettres[i];
            for (char c = 'a'; c <= 'z'; c++) {
                lettres[i] = c;
                String voisin = String.valueOf(lettres);
                if (carteDistances.containsKey(voisin) && carteDistances.get(voisin) == distCible - 1) {
                    chemin.add(voisin);
                    backtrack(voisin, cible, chemin);
                    chemin.removeLast();
                }
            }
            lettres[i] = temp;
        }
    }
}

L'optimisation clé ici est l'utilisation de la carte des distances. Lors de la phase de backtracking, nous ne testons que les mots dont la distance est inférieure d'une unité, ce qui élimine les cycles et les chemins sous-optimaux dès le départ.