Comment vérifier si deux chaînes de caractères ont une distance d'édition de un ? (Techniques et Exemples)

Vous vous demandez comment déterminer rapidement si deux chaînes de caractères sont proches, à une seule modification près ? Découvrez les méthodes efficaces pour calculer la "distance d'édition" et les algorithmes pour optimiser cette vérification.

Pourquoi est-ce important de vérifier la distance d'édition ?

Comprendre la distance d'édition vous permet de :

• Corriger automatiquement des erreurs de frappe : Proposez des suggestions de mots proches en cas de fautes de frappe.
• Comparer des séquences d'ADN : Identifier des mutations génétiques mineures.
• Améliorer la recherche : Trouvez des résultats pertinents même si l'utilisateur fait une petite erreur dans sa requête.
• Valider des données : Assurez-vous que les entrées utilisateur respectent un format attendu avec une tolérance pour les erreurs mineures.

Qu'est-ce que la distance d'édition ?

La distance d'édition (ou distance de Levenshtein) entre deux chaînes de caractères est le nombre minimal d'opérations nécessaires pour transformer une chaîne en l'autre. Les opérations autorisées sont :

• Insertion : Ajouter un caractère.
• Suppression : Supprimer un caractère.
• Substitution : Remplacer un caractère par un autre.

Dans cet article, nous cherchons spécifiquement à savoir si la distance d'édition est égale à un. Cela signifie qu'une seule de ces opérations est suffisante pour transformer une chaîne en l'autre.

Algorithme efficace pour vérifier une distance d'édition de un

L'algorithme suivant permet de déterminer si deux chaînes de caractères s1 et s2 ont une distance d'édition de un, en optimisant le temps d'exécution:

1. Vérification de la longueur : Si la différence de longueur entre s1 et s2 est supérieure à 1, renvoyez false. Une seule opération ne peut pas combler un écart aussi important.

2. Initialisation : Initialisez un compteur d'éditions à 0.

3. Parcours simultané : Parcourez les deux chaînes de caractères simultanément.

   • a) Différence détectée : Si les caractères actuels ne correspondent pas :

     • Incrémentez le compteur d'éditions.
     • Si le compteur dépasse 1, renvoyez false (plus d'une édition nécessaire).
     • Si la longueur d'une chaîne est supérieure à l'autre, avancez uniquement dans la chaîne la plus longue (suppression implicite).
     • Sinon (longueurs égales), avancez dans les deux chaînes (substitution implicite).

   • b) Correspondance : Si les caractères correspondent, avancez dans les deux chaînes.

4. Caractères restants : Après le parcours, s'il reste des caractères dans l'une des chaînes, incrémentez le compteur (insertion/suppression à la fin).

5. Résultat : Renvoyez true si le compteur d'éditions est égal à 1, sinon false.

Exemples concrets

Analysons quelques exemples pour illustrer l'algorithme.

• "geeks", "geek" : Une suppression ("s") suffit. Sortie : Oui
• "geeks", "geeks" : Aucune modification nécessaire. Sortie : Non
• "geaks", "geeks" : Une substitution ("a" -> "e") suffit. Sortie : Oui
• "peaks", "geeks" : Deux substitutions ("p" -> "g", "a" -> "e"). Sortie : Non

Implementations dans différents langages

Vous trouverez ci-dessous des exemples de code pour différents langages.

C++

#include <iostream>
#include <string>
#include <algorithm>

using namespace std;

bool isEditDistanceOne(string s1, string s2) {
  int m = s1.length(), n = s2.length();

  if (abs(m - n) > 1)
    return false;

  int count = 0;
  int i = 0, j = 0;

  while (i < m && j < n) {
    if (s1[i] != s2[j]) {
      if (count == 1)
        return false;

      if (m > n)
        i++;
      else if (m < n)
        j++;
      else {
        i++;
        j++;
      }
      count++;
    } else {
      i++;
      j++;
    }
  }

  if (i < m || j < n)
    count++;

  return count == 1;
}

int main() {
  string s1 = "gfg";
  string s2 = "gf";
  if(isEditDistanceOne(s1, s2)){
      cout << "Yes" << endl;
  } else {
      cout << "No" << endl;
  }
  return 0;
}

Java

class GFG {
    static boolean isEditDistanceOne(String s1, String s2) {
        int m = s1.length(), n = s2.length();

        if (Math.abs(m - n) > 1)
            return false;

        int count = 0;
        int i = 0, j = 0;

        while (i < m && j < n) {
            if (s1.charAt(i) != s2.charAt(j)) {
                if (count == 1)
                    return false;

                if (m > n)
                    i++;
                else if (m < n)
                    j++;
                else {
                    i++;
                    j++;
                }
                count++;
            } else {
                i++;
                j++;
            }
        }

        if (i < m || j < n)
            count++;

        return count == 1;
    }

    public static void main(String[] args) {
        String s1 = "gfg";
        String s2 = "gf";
        if (isEditDistanceOne(s1, s2))
            System.out.print("Yes");
        else
            System.out.print("No");
    }
}

Python

def isEditDistanceOne(s1, s2):
    m = len(s1)
    n = len(s2)

    if abs(m - n) > 1:
        return False

    count = 0
    i = 0
    j = 0

    while i < m and j < n:
        if s1[i] != s2[j]:
            if count == 1:
                return False

            if m > n:
                i += 1
            elif m < n:
                j += 1
            else:
                i += 1
                j += 1
            count += 1
        else:
            i += 1
            j += 1

    if i < m or j < n:
        count += 1

    return count == 1

s1 = "gfg"
s2 = "gf"
if isEditDistanceOne(s1, s2):
    print("Yes")
else:
    print("No")

C#

using System;

class GFG {
    static bool isEditDistanceOne(String s1, String s2) {
        int m = s1.Length, n = s2.Length;

        if (Math.Abs(m - n) > 1)
            return false;

        int count = 0;
        int i = 0, j = 0;

        while (i < m && j < n) {
            if (s1[i] != s2[j]) {
                if (count == 1)
                    return false;

                if (m > n)
                    i++;
                else if (m < n)
                    j++;
                else {
                    i++;
                    j++;
                }
                count++;
            } else {
                i++;
                j++;
            }
        }

        if (i < m || j < n)
            count++;

        return count == 1;
    }

    public static void Main() {
        String s1 = "gfg";
        String s2 = "gf";
        if (isEditDistanceOne(s1, s2))
            Console.WriteLine("Yes");
        else
            Console.WriteLine("No");
    }
}

JavaScript

function isEditDistanceOne(s1, s2) {
    let m = s1.length, n = s2.length;

    if (Math.abs(m - n) > 1)
        return false;

    let count = 0;
    let i = 0, j = 0;

    while (i < m && j < n) {
        if (s1[i] != s2[j]) {
            if (count == 1)
                return false;

            if (m > n)
                i++;
            else if (m < n)
                j++;
            else {
                i++;
                j++;
            }
            count++;
        } else {
            i++;
            j++;
        }
    }

    if (i < m || j < n)
        count++;

    return count == 1;
}

let s1 = "gfg";
let s2 = "gf";
if (isEditDistanceOne(s1, s2)) {
    console.log("Yes");
} else {
    console.log("No");
}

Optimisations possibles

• Arrêt précoce : Si les chaînes sont identiques, renvoyez false immédiatement.
• Pré-calcul de la longueur : Stockez les longueurs des chaînes dans des variables pour éviter des appels multiples à la fonction length().

Conclusion

Cet algorithme efficace vous permet de déterminer rapidement si deux chaînes de caractères sont à une distance d'édition de un. Utilisez-le pour corriger les erreurs, comparer des données, et améliorer vos applications. N'hésitez pas à adapter les implémentations fournies à votre langage de programmation favori.