How to Check if Two Strings Have an Edit Distance of One: A Practical Guide

Ever needed to know if two strings are just one edit away from being the same? Whether you're validating user input, correcting typos, or working with DNA sequences, determining if the "edit distance" between two strings is one can be incredibly useful. This article breaks down the concept, provides a clear algorithm, and gives you code examples in multiple languages.

Understanding Edit Distance

Edit distance refers to the minimum number of single-character edits required to change one string into another. These edits can be:

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

When we say two strings have an edit distance of one, it means you can transform one string into the other with just one of these operations.

Why is This Important?

• Spell Checkers: Suggesting corrections for misspelled words.
• Bioinformatics: Analyzing DNA sequences and identifying mutations.
• Data Validation: Ensuring data conforms to expected patterns with minimal errors.
• Search Algorithms: Fuzzy search, finding similar entries even with slight variations.

The Efficient Algorithm Explained

Instead of using more complex dynamic programming techniques, we can determine if two strings are one edit away using a single pass! This approach boasts a time complexity of O(m+n), where 'm' and 'n' are the lengths of the strings.

Here’s the step-by-step breakdown:

1. Length Check: If the difference in length between the two strings is more than 1, they can't be one edit away. Return false.
2. Initialization: Set an editCount to 0. This variable tracks the number of edits found.
3. Simultaneous Traversal: Use two pointers to walk through both strings, character by character.
   • Mismatch: If the characters at the current pointers don't match:
     • Increment editCount. If editCount exceeds 1, return false.
     • If the strings have different lengths, advance the pointer in the longer string.
     • If the strings have the same length, advance both pointers (substitution).
   • Match: If the characters match, advance both pointers.
4. Trailing Character: If one string has a remaining character after the loop finishes, increment editCount.
5. Final Check: Return true if editCount is exactly 1; otherwise, return false.

Code Implementation Examples

Here are code examples in various popular programming languages:

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";
    cout << (isEditDistanceOne(s1, s2) ? "Yes" : "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";
        System.out.println(isEditDistanceOne(s1, s2) ? "Yes" : "No");
    }
}

Python3 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"
print("Yes" if isEditDistanceOne(s1, s2) else "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 s1 = "gfg";
        string s2 = "gf";
        Console.WriteLine(isEditDistanceOne(s1, s2) ? "Yes" : "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";
console.log(isEditDistanceOne(s1, s2) ? "Yes" : "No");

Key Takeaways

• Checking for an edit distance of one is useful in various applications, from spell checking to bioinformatics.
• The efficient algorithm presented here has a time complexity of O(m+n).
• You can easily implement this algorithm in multiple languages.

By using this guide, you can confidently determine whether two strings are just one edit away from each other!