One Edit Distance

How it works

Two strings are one edit distance apart if we can transform one into the other with exactly one operation: insert, delete, or replace a single character. The key insight is that the length difference between the strings tells us which operation is possible.

If the lengths differ by more than 1, it is impossible to make them equal with one edit. If they have the same length, we need exactly one replacement. If they differ by 1, we need exactly one insertion or deletion.

We scan both strings in parallel. When we find the first mismatch, we check if the remaining portions match according to the appropriate rule.

Steps

1. Ensure s is the shorter string by swapping if necessary.
2. If the length difference is greater than 1, return false.
3. Iterate through the shorter string character by character:
   • When we find a mismatch at position i:
     • If lengths are equal, check if s[i+1:] equals t[i+1:] (one replacement).
     • If lengths differ, check if s[i:] equals t[i+1:] (one deletion from t).
4. If no mismatch is found, return true only if t has exactly one more character (the edit is appending to s).

Complexity

• Time complexity: O(N) in the worst case when string lengths are close enough abs(ns - nt) <= 1. O(1) in the best case when abs(ns - nt) > 1
• Space complexity: O(N) extra space used

where N is the number of characters in the longest string

Things to watch for

Returning True for Identical Strings

A common mistake is returning true when both strings are exactly identical. The problem requires exactly one edit, so identical strings should return false. Always check that strings differ by exactly one operation.

Forgetting the Append/Delete at End Case

When no mismatch is found during the loop, some solutions incorrectly return false. If the shorter string is a prefix of the longer string and the longer string has exactly one more character, the answer is true. This edge case occurs when the edit is appending a character at the end.

Not Handling the Length Difference Correctly

When strings have different lengths, the comparison after finding a mismatch must skip the extra character in the longer string, not the shorter one. Confusing which string to advance leads to incorrect substring comparisons and wrong answers for insertion/deletion cases.

class Solution:
    def isOneEditDistance(self, s: "str", t: "str") -> "bool":
        ns, nt = len(s), len(t)

        # Ensure that s is shorter than t.
        if ns > nt:
            return self.isOneEditDistance(t, s)

        # The strings are NOT one edit away from distance
        # if the length diff is more than 1.
        if nt - ns > 1:
            return False

        for i in range(ns):
            if s[i] != t[i]:
                # If strings have the same length
                if ns == nt:
                    return s[i + 1 :] == t[i + 1 :]
                # If strings have different lengths
                else:
                    return s[i:] == t[i + 1 :]

        # If there are no diffs in ns distance
        # The strings are one edit away only if
        # t has one more character.
        return ns + 1 == nt

class Solution {
public:
    bool isOneEditDistance(string s, string t) {
        int ns = s.size();
        int nt = t.size();

        // Ensure that s is shorter than t.
        if (ns > nt) return isOneEditDistance(t, s);

        // The strings are NOT one edit away distance
        // if the length diff is more than 1.
        if (nt - ns > 1) return false;

        for (int i = 0; i < ns; i++)
            if (s[i] != t[i])
                // if strings have the same length
                if (ns == nt) return s.substr(i + 1) == t.substr(i + 1);
                // If strings have different lengths
                else
                    return s.substr(i) == t.substr(i + 1);

        // If there are no diffs in ns distance
        // The strings are one edit away only if
        // t has one more character.
        return (ns + 1 == nt);
    }
};