Défi de conversion de mots - Programmation compétitive

Distance d'édition — Problème de Levenshtein

Un enseignant de français dans une école primaire veut motiver ses élèves à apprendre l'alphabet et à comparer des mots en créant des activités amusantes.

Dans l'une des activités, l'enseignant choisit au hasard deux élèves, puis chaque élève écrit un mot au tableau, et l'enseignant demande aux autres élèves combien d'opérations ont été nécessaires pour convertir le premier mot (mot1) en deuxième (mot2).

Le premier élève qui a réussi à convertir le premier mot en second en un nombre minimum d'opérations reçoit une barre de chocolat.

Définition — Distance d'édition (Levenshtein) La distance d'édition entre deux chaînes de caractères est le nombre minimal d'opérations nécessaires pour transformer une chaîne en une autre.

Les opérations autorisées sont :

Insérer : ajouter un caractère à la chaîne
Supprimer : supprimer un caractère
Remplacer : remplacer un caractère par un autre

Ce problème est un classique de la programmation dynamique.

Énoncé du problème

Entrée

Une ligne contient les deux mots séparés par un espace : mot1 et mot2.

Sortie

Le nombre minimum d'opérations requises pour convertir mot1 en mot2.

Exemple 1

Entrée

bonsoir bonjour

Sortie

Explication : Il faut remplacer 's' par 'j' et 'i' par 'u' → 2 opérations.

Exemple 2

Entrée

meknes meknes

Sortie

Explication : Les deux mots sont identiques → 0 opération.

Exemple 3

Entrée

hllo hello

Sortie

Explication : Il faut insérer un 'e' après 'h' → 1 opération.

Contraintes

Les mots peuvent contenir uniquement des lettres minuscules.
1 ≤ longueur(mot) ≤ 10³

Solution naïve — Récursive

L'idée est de traiter tous les caractères un par un en partant du côté droit des deux mots. Soient m et n les longueurs respectives de mot1 et mot2.

Il y a deux possibilités pour chaque paire de caractères en cours de traitement :

Cas 1 : Si les derniers caractères des deux mots sont identiques, rien à faire. On ignore ces caractères et on récure pour les longueurs m-1 et n-1.
Cas 2 : Sinon (les derniers caractères sont différents), on considère les trois opérations possibles sur le dernier caractère de mot1:
- Insérer : on récure pour m et n-1
- Supprimer : on récure pour m-1 et n
- Remplacer : on récure pour m-1 et n-1
On prend le minimum des trois et on ajoute 1 (l'opération courante).

Cas de base de la récursion C++/Python

si m == 0 → retourner n   // insérer tous les caractères de mot2
si n == 0 → retourner m   // supprimer tous les caractères de mot1

#include <iostream>
#include <string>
#include <algorithm>
using namespace std;

int minOperations(string &mot1, string &mot2, int m, int n) {
    // Cas de base
    if (m == 0) return n;
    if (n == 0) return m;
    
    // Si les derniers caractères sont identiques
    if (mot1[m-1] == mot2[n-1])
        return minOperations(mot1, mot2, m-1, n-1);
    
    // Sinon, prendre le minimum des trois opérations
    return 1 + min({
        minOperations(mot1, mot2, m, n-1),   // Insérer
        minOperations(mot1, mot2, m-1, n),   // Supprimer
        minOperations(mot1, mot2, m-1, n-1)  // Remplacer
    });
}

int main() {
    string mot1, mot2;
    cin >> mot1 >> mot2;
    cout << minOperations(mot1, mot2, mot1.size(), mot2.size());
    return 0;
}

import sys

def minOperations(mot1, mot2, m, n):
    # Cas de base
    if m == 0:
        return n
    if n == 0:
        return m
    
    # Si les derniers caractères sont identiques
    if mot1[m-1] == mot2[n-1]:
        return minOperations(mot1, mot2, m-1, n-1)
    
    # Sinon, prendre le minimum des trois opérations
    return 1 + min(
        minOperations(mot1, mot2, m, n-1),   # Insérer
        minOperations(mot1, mot2, m-1, n),   # Supprimer
        minOperations(mot1, mot2, m-1, n-1)  # Remplacer
    )

mot1, mot2 = sys.stdin.readline().strip().split()
print(minOperations(mot1, mot2, len(mot1), len(mot2)))

Complexité — Solution récursive naïve Dans le pire des cas, la récursion explore tous les chemins possibles.
Complexité temporelle : O(3^max(m,n)) — exponentielle.
Complexité spatiale : O(max(m,n)) — profondeur de la pile d'appels.

Le pire cas se produit lorsqu'aucun des caractères des deux mots ne correspond.

Solution optimale — Programmation Dynamique (Bottom-Up)

Pour résoudre le problème en temps polynomial, on utilise la programmation dynamique avec un tableau 2D.

Définition — Tableau DP On crée un tableau d'entiers dp[m+1][n+1] où :

dp[i][j] = nombre minimum d'opérations pour convertir les i premiers caractères de mot1 en les j premiers caractères de mot2.

Règle de remplissage du tableau

Initialisation :
- dp[i][0] = i pour tout i (supprimer i caractères)
- dp[0][j] = j pour tout j (insérer j caractères)
Récurrence :Pour i de 1 à m, j de 1 à n
- Si mot1[i-1] == mot2[j-1] → dp[i][j] = dp[i-1][j-1]
- Sinon → dp[i][j] = 1 + min(
  - dp[i][j-1] (insérer)
  - dp[i-1][j] (supprimer)
  - dp[i-1][j-1] (remplacer)
  )

Illustration — conversion de "bonsoir" en "bonjour"

	j=0	1 (b)	2 (o)	3 (n)	4 (j)	5 (o)	6 (u)	7 (r)
i=0	0	1	2	3	4	5	6	7
1 (b)	1	0	1	2	3	4	5	6
2 (o)	2	1	0	1	2	3	4	5
3 (n)	3	2	1	0	1	2	3	4
4 (s)	4	3	2	1	1	2	3	4
5 (o)	5	4	3	2	2	1	2	3
6 (i)	6	5	4	3	3	2	2	3
7 (r)	7	6	5	4	4	3	3	2

dp[7][7] = 2 → 2 opérations

#include <iostream>
#include <string>
#include <algorithm>
using namespace std;

int minOperations(string &mot1, string &mot2, int m, int n) {
    // Tableau DP de taille (m+1) x (n+1)
    int dp[m+1][n+1];
    
    // Initialisation
    for (int i = 0; i <= m; i++)
        dp[i][0] = i;  // Supprimer i caractères
    
    for (int j = 0; j <= n; j++)
        dp[0][j] = j;  // Insérer j caractères
    
    // Remplissage du tableau
    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= n; j++) {
            if (mot1[i-1] == mot2[j-1])
                dp[i][j] = dp[i-1][j-1];
            else
                dp[i][j] = 1 + min({dp[i][j-1],        // Insérer
                                    dp[i-1][j],        // Supprimer
                                    dp[i-1][j-1]});    // Remplacer
        }
    }
    
    return dp[m][n];
}

int main() {
    string mot1, mot2;
    cin >> mot1 >> mot2;
    cout << minOperations(mot1, mot2, mot1.size(), mot2.size());
    return 0;
}

import sys

def minOperations(mot1, mot2, m, n):
    # Tableau DP de taille (m+1) x (n+1)
    dp = [[0] * (n + 1) for _ in range(m + 1)]
    
    # Initialisation
    for i in range(m + 1):
        dp[i][0] = i  # Supprimer i caractères
    
    for j in range(n + 1):
        dp[0][j] = j  # Insérer j caractères
    
    # Remplissage du tableau
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if mot1[i-1] == mot2[j-1]:
                dp[i][j] = dp[i-1][j-1]
            else:
                dp[i][j] = 1 + min(dp[i][j-1],        # Insérer
                                   dp[i-1][j],        # Supprimer
                                   dp[i-1][j-1])       # Remplacer
    
    return dp[m][n]

mot1, mot2 = sys.stdin.readline().strip().split()
print(minOperations(mot1, mot2, len(mot1), len(mot2)))

Sortie (Exemple 1)

Complexité — Solution Programmation Dynamique

Critère	Solution récursive naïve	Programmation dynamique
Temps	O(3^max(m,n)) — exponentiel	O(m × n) — polynomial
Espace	O(max(m,n)) — pile d'appels	O(m × n) — tableau 2D
Sous-problèmes recalculés	Oui — nombreux recalculs	Non — mémoïsation implicite

Optimisation mémoire — Tableau 2 lignes On peut réduire l'espace à O(min(m,n))en remarquant que pour calculer la ligne i, on a seulement besoin de la ligne i-1.

vector<int> prev(n+1), curr(n+1);
for (int j = 0; j <= n; j++) prev[j] = j;  // i=0
for (int i = 1; i <= m; i++) {
    curr[0] = i;  // j=0
    for (int j = 1; j <= n; j++) {
        if (mot1[i-1] == mot2[j-1])
            curr[j] = prev[j-1];
        else
            curr[j] = 1 + min({curr[j-1], prev[j], prev[j-1]});
    }
    swap(prev, curr);
}
return prev[n];

Points clés à retenir

La distance d'édition (Levenshtein) mesure le nombre minimal d'opérations (insertion, suppression, remplacement) pour transformer une chaîne en une autre.
La solution récursive naïve a une complexité exponentielle O(3^max(m,n)).
La programmation dynamique permet de résoudre le problème en temps polynomial O(m × n).
Le tableau DP dp[i][j] représente le coût minimum pour convertir les i premiers caractères de mot1 en les j premiers de mot2.
La relation de récurrence est :
- Si caractères égaux : dp[i][j] = dp[i-1][j-1]
- Sinon : dp[i][j] = 1 + min(dp[i][j-1], dp[i-1][j], dp[i-1][j-1])
Une optimisation mémoire permet de réduire l'espace à O(min(m,n)).

Sortie

// La sortie apparaîtra ici…

Prêt · Ctrl+Entrée pour exécuter

Défi de conversion de mots - Programmation compétitive

Distance d'édition — Problème de Levenshtein

Énoncé du problème

Entrée

Sortie

Solution naïve — Récursive

Solution optimale — Programmation Dynamique (Bottom-Up)

Discussion (0)

Laisser un commentaire

Structures de données

Algorithmes

Programmation

Bases de données

CPGE

Modules informatique

Défi de conversion de mots - Programmation compétitive

Distance d'édition — Problème de Levenshtein

Énoncé du problème

Entrée

Sortie

Solution naïve — Récursive

Solution optimale — Programmation Dynamique (Bottom-Up)

Discussion (0)

Laisser un commentaire