Comment vérifier rapidement si deux chaînes sont à une distance d'édition l'une de l'autre ?

Vous vous demandez si deux chaînes de caractères diffèrent d'une seule modification ? Découvrez une méthode rapide et efficace pour le déterminer. Cet article vous propose un guide clair et concis, accompagné d'exemples concrets.

Comprendre la notion de distance d'édition : 1 modification suffit !

La distance d'édition d'une seule unité signifie que l'on peut transformer une chaîne en une autre par une seule des actions suivantes:

• Ajout d'un caractère.
• Suppression d'un caractère.
• Modification d'un caractère.

Pourquoi s'intéresser à la distance d'édition ?

• Correction orthographique : Détecter les erreurs de frappe courantes.
• Recherche approximative : Trouver des correspondances proches dans une base de données.
• Bio-informatique : Comparer des séquences d'ADN.

Algorithme efficace : Vérification pas à pas

Au lieu d'une solution complexe en O(n^2), adoptons une approche linéaire en O(m+n), où m et n sont les longueurs des chaînes.

Étapes clés :

1. Vérification préliminaire de la longueur : Si la différence de longueur dépasse 1, c'est impossible ! La fonction renvoie immédiatement false.
2. Initialisation : Un compteur d'éditions est initialisé à 0.
3. Parcours simultané : Les deux chaînes sont parcourues caractère par caractère.
   • Divergence détectée :
     • Le compteur d'éditions est incrémenté.
     • Si le compteur dépasse 1, la fonction renvoie false (trop de différences !).
     • La chaîne la plus longue est avancée (suppression implicite), ou les deux si le changement est une substitution.
   • Correspondance : Les deux indices sont incrémentés.
4. Caractère final : Si une chaîne a encore un caractère à la fin, incrémenter le compteur.
5. Verdict : Retourner true si le compteur d'éditions vaut exactement 1. Sinon, retourner false.

Exemples concrets pour une compréhension immédiate

• s1 = "geeks", s2 = "geek" : Oui, une suppression.
• s1 = "geeks", s2 = "geeks" : Non, aucune modification.
• s1 = "geaks", s2 = "geeks" : Oui, une modification.
• s1 = "peaks", s2 = "geeks" : Non, deux modifications.

Implémentations dans différents langages

Des exemples d'implémentation sont proposés en C++, Java, Python3, C# et Javascript :

// C++ program to check if given two strings are
// at distance one.
#include <iostream>
#include <string>

using namespace std;

// Returns true if edit distance between s1 and
// s2 is one, else false
bool isEditDistanceOne(string s1, string s2) {
    // Find lengths of given strings
    int m = s1.length(), n = s2.length();

    // If difference between lengths is more than
    // 1, then strings can't be at one distance
    if (abs(m - n) > 1)
        return false;

    int count = 0;  // Count of edits
    int i = 0, j = 0;
    while (i < m && j < n) {
        // If current characters don't match
        if (s1[i] != s2[j]) {
            // If you have already found one difference, return false
            if (count == 1)
                return false;

            // If length of one string is
            // more, then only possible edit
            // is to remove a character
            if (m > n)
                i++;
            else if (m < n)
                j++;
            else { // If lengths of both strings is same
                i++;
                j++;
            }

            // Increment count of edits
            count++;
        } else { // If current characters match
            i++;
            j++;
        }
    }

    // If last character is extra in any string
    if (i < m || j < n)
        count++;

    return count == 1;
}

// Driver program
int main() {
    string s1 = "gfg";
    string s2 = "gf";

    if (isEditDistanceOne(s1, s2))
        cout << "Yes";
    else
        cout << "No";
    return 0;
}

Tableaux comparatifs : Une vue d'ensemble

(L'article original contient des tableaux pour chaque langage, mais ils seraient trop longs à reproduire ici. Je vous encourage à consulter l'article source pour les implémentations complètes.)

Conclusion: Simplicité et efficacité

Cet algorithme simple et performant permet de déterminer rapidement si deux chaînes sont à une distance d'édition de un, ouvrant la porte à de nombreuses applications pratiques. Ne passez plus des heures sur des algorithmes complexes, concentrez-vous sur l'essentiel !