Défi de conversion de mots - Programmation compétitive
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 de convertir le premier mot en second en un nombre minimum d'opérations reçoit une barre de chocolat.
Les opérations autorisées pour convertir les mots sont les suivantes
- Insérer : ajouter un caractère au mot
- Supprimer : supprimer un caractère
- Remplacer : remplacer un caractère
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.
Exemples
| Entrée du programme | Sortie du programme |
|---|---|
| bonsoir bonjour | 2 |
| meknes meknes | 0 |
| hllo hello | 1 |
Solution naive (récursive)
L'idée est de traiter tous les caractères un par un en partant du côté gauche ou droit des deux mots.
la longueur des mots mot1 et mot2 sont respectivement m et n
il y a deux possibilités pour chaque paire de caractères en cours de traitement.
- Si les derniers caractères de deux mots sont identiques, rien à faire. Ignorer les derniers caractères et obtenir le nombre d'opérations pour les caractères restants. On récure donc pour les longueurs m-1 et n-1.
- Sinon (si les derniers caractères ne sont pas les mêmes), nous considérons toutes les opérations sur 'mot1', considérons les trois opérations sur le dernier caractère du premier mot, calculons récursivement le nombre minimum d'opérations pour les trois opérations et prenons le minimum de trois.
- Insérer : Nous récurons pour m et n-1
- Supprimer : Nous récurons pour m-1 et n
- Remplacer : Nous récurons pour m-1 et n-1
#include <iostream>
#include <string>
using namespace std;
int minOperations(string &mot1, string &mot2, int m, int n){
/*
Si le premier mot est vide, la seule option est
d'insérer tous les caractères du deuxième mot dans le premier
*/
if (m == 0)
return n;
/*
Si le deuxième mot est vide, la seule option
est de supprimer tous les caractères du premier mot
*/
if (n == 0)
return m;
// Option 1
// Les derniers caractères de deux mots sont identiques
if (mot1[m-1] == mot2[n-1])
return minOperations(mot1, mot2, m-1, n-1);
// option2
return 1 + min(minOperations(mot1, mot2, m, n-1),min( // 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):
# Si le premier mot est vide, la seule option est
# d'insérer tous les caractères du deuxième mot dans le premier
if m == 0:
return n
# Si le deuxième mot est vide, la seule option
# est de supprimer tous les caractères du premier mot
if n == 0:
return m
# Option 1
# Les derniers caractères de deux mots sont identiques
if mot1[m-1] == mot2[n-1]:
return minOperations(mot1, mot2, m-1, n-1)
# option2
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=map(str, sys.stdin.readline().strip().split())
print(minOperations(mot1,mot2,len(mot1),len(mot2)))
Complexité :
La complexité temporelle de la solution ci-dessus est exponentielle. Dans le pire des cas, nous pouvons finir par faire \(O(3^m)\) opérations. Le pire des cas se produit lorsqu'aucun des caractères de deux mots ne correspond.
Solution optimale (Programmation dynamique)
#include <iostream>
#include <string>
using namespace std;
// approche bottom-up
int minOperations(string &mot1, string &mot2, int m, int n){
// Tableau qui stocke les résultats des sous-problèmes
int dp[m+1][n+1];
for (int i = 0; i <= m; i++) {
for (int j = 0; j <= n; j++) {
// Si le premier mot est vide, la seule option est
// d'insérer tous les caractères du deuxième mot dans le premier
if (i == 0)
dp[i][j] = j; // Min. operations = j
// Si le deuxième mot est vide, la seule option
// est de supprimer tous les caractères du premier mot
else if (j == 0)
dp[i][j] = i; // Min. operations = i
// Option 1
// Les derniers caractères de deux mots sont identiques
else if (mot1[i-1] == mot2[j-1])
dp[i][j] = dp[i-1][j-1];
// Option 2
else
dp[i][j] = 1 + min(dp[i][j-1], // Insérer
min(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
# approche bottom-up
def minOperations(str1, str2, m, n):
# Tableau qui stocke les résultats des sous-problèmes
dp = [[0 for x in range(n + 1)] for x in range(m + 1)]
for i in range(m + 1):
for j in range(n + 1):
# # Si le premier mot est vide, la seule option est
# d'insérer tous les caractères du deuxième mot dans le premier
if i == 0:
dp[i][j] = j # Min. operations = j
# Si le deuxième mot est vide, la seule option
# est de supprimer tous les caractères du premier mot
elif j == 0:
dp[i][j] = i # Min. operations = i
# Option 1
# Les derniers caractères de deux mots sont identiques
elif str1[i-1] == str2[j-1]:
dp[i][j] = dp[i-1][j-1]
# Option 2
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=map(str, sys.stdin.readline().strip().split())
print(minOperations(mot1,mot2,len(mot1),len(mot2)))
Complexité :
- Complexité temporelle : O(m*n)
- Complexité spatiale : O(m*n)
