Check String Edit Distance: Simple Guide with C++, Java, Python, C#, and JavaScript Examples

Want to quickly determine if two strings are just one edit away from each other? This guide breaks down the concept of "edit distance" and provides efficient algorithms to check if two strings are within one edit – whether it's adding, deleting, or changing a single character. Plus, we've included ready-to-use code examples in C++, Java, Python, C#, and JavaScript. Let's dive in and simplify your string comparisons!

What is Edit Distance? Understanding Single-Edit String Differences

The edit distance between two strings quantifies how different they are by counting the minimum number of edits required to transform one string into the other. These edits can be:

• Insertion: Adding a character.
• Deletion: Removing a character.
• Substitution: Changing a character.

This article focuses on determining if the edit distance is exactly one, meaning only one of these operations is needed to make the strings identical

Why Check for an Edit Distance of One? Practical Applications

Checking for a single edit distance has several practical applications:

• Spell Checkers: Suggesting corrections for misspelled words.
• Data Cleaning: Identifying and correcting minor errors in datasets.
• Bioinformatics: Analyzing DNA sequences with slight variations.
• Search Algorithms: Improving search results by considering near-matches.

The Efficient Algorithm: How to Check Edit Distance of One

Instead of using complex dynamic programming, we can efficiently check for an edit distance of one by traversing both strings simultaneously. Here's the breakdown:

1. Length Difference: If the absolute difference in lengths of the two strings is more than 1, they can't be at an edit distance of one. Return false.

2. Initialize: Set an edit_count to 0 and use pointers i and j to traverse string1 and string2 respectively.

3. Simultaneous Traversal: Iterate through the strings while i is less than the length of string1 AND j is less than the length of string2.

   • Mismatch: If characters at string1[i] and string2[j] don't match:

     • Increment edit_count.
     • If edit_count exceeds 1, return false.
     • If string1 is longer, increment i (simulating a deletion from string1).
     • Else if string2 is longer, increment j (simulating an insertion in string1).
     • Otherwise, increment both i and j (simulating a substitution).

   • Match: If characters match, increment both i and j.

4. Handle Remaining Characters: After the loop, if there are any remaining characters in either string, increment edit_count.

5. Final Check: Return true if edit_count is exactly 1; otherwise, return false.

Code Implementation in Multiple Languages

Below are implementations of the algorithm in C++, Java, Python, C#, and JavaScript:

C++ Implementation

#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 Implementation

class Main {
    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.println("Yes");
        else
            System.out.println("No");
    }
}

Python Implementation

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# Implementation

using System;

public class Program
{
    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[] args)
    {
        string s1 = "gfg";
        string s2 = "gf";
        if (isEditDistanceOne(s1, s2))
            Console.WriteLine("Yes");
        else
            Console.WriteLine("No");
    }
}

JavaScript Implementation

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");
}

Summary: Quick and Efficient Edit Distance Checks

This guide offers a straightforward and efficient way to check if two strings are within an edit distance of one, complete with code examples across multiple popular programming languages. This is valuable for various applications including spell checking, data validation, and more. Implement these algorithms to enhance your projects with rapid string comparison capabilities.