Code Implementation

class Solution:
    def isOneEditDistance(self, s: str, t: str) -> bool:
        m, n = len(s), len(t)
        # Ensure s is the shorter string
        if m > n:
            return self.isOneEditDistance(t, s)
        # Length difference > 1 means more than one edit
        if n - m > 1:
            return False
        for i in range(m):
            if s[i] != t[i]:
                if m == n:
                    # Replace operation
                    return s[i+1:] == t[i+1:]
                else:
                    # Insert operation in s or delete in t
                    return s[i:] == t[i+1:]
        # All previous chars are the same, last char can be extra in t
        return n - m == 1
      

class Solution {
public:
    bool isOneEditDistance(string s, string t) {
        int m = s.size(), n = t.size();
        if (m > n) return isOneEditDistance(t, s);
        if (n - m > 1) return false;
        for (int i = 0; i < m; ++i) {
            if (s[i] != t[i]) {
                if (m == n)
                    return s.substr(i+1) == t.substr(i+1);
                else
                    return s.substr(i) == t.substr(i+1);
            }
        }
        return n - m == 1;
    }
};
      

class Solution {
    public boolean isOneEditDistance(String s, String t) {
        int m = s.length(), n = t.length();
        if (m > n) return isOneEditDistance(t, s);
        if (n - m > 1) return false;
        for (int i = 0; i < m; i++) {
            if (s.charAt(i) != t.charAt(i)) {
                if (m == n)
                    return s.substring(i+1).equals(t.substring(i+1));
                else
                    return s.substring(i).equals(t.substring(i+1));
            }
        }
        return n - m == 1;
    }
}
      

var isOneEditDistance = function(s, t) {
    let m = s.length, n = t.length;
    if (m > n) return isOneEditDistance(t, s);
    if (n - m > 1) return false;
    for (let i = 0; i < m; i++) {
        if (s[i] !== t[i]) {
            if (m === n)
                return s.substring(i+1) === t.substring(i+1);
            else
                return s.substring(i) === t.substring(i+1);
        }
    }
    return n - m === 1;
};
      

Problem Description

Given two strings, s and t, determine if they are exactly one edit distance apart. An edit is defined as one of the following operations:

• Insert a single character into s to get t
• Delete a single character from s to get t
• Replace a single character in s to get t

The function should return true if you can transform s into t with exactly one edit, and false otherwise.

Constraints:

• Both s and t are non-null strings (may be empty).
• Only one edit is allowed; more than one edit or zero edits (identical strings) should return false.
• Edits cannot be combined; only a single operation is allowed.

Thought Process

To solve this problem, we first consider the definition of "one edit distance." The two strings must differ by exactly one simple operation: insert, delete, or replace a single character. If the strings are identical, then zero edits are needed, so we return false. If the length difference is more than one, it's impossible to make them match with a single edit.

Brute force might suggest generating all possible one-edit variations of s and checking if t is among them, but this is inefficient, especially for longer strings. Instead, we can compare the strings character by character and identify the first difference. At that point, we can check if a single operation would make the rest of the strings match.

We also notice that the three operations can be unified by always comparing the shorter string to the longer one. This allows us to handle insertion and deletion as two sides of the same coin.

Solution Approach

• Step 1: Compare the lengths of s and t. Always treat s as the shorter or equal-length string. If not, swap them.
• Step 2: If the length difference is greater than 1, return false because more than one edit would be needed.
• Step 3: Iterate through the characters of s (the shorter string). For each character, compare it with the corresponding character in t.
• Step 4: On finding the first mismatch:
  • If lengths are equal, check if the substrings after this index are equal. This simulates a replace operation.
  • If t is longer by one, check if the substring of s from this index matches the substring of t from the next index. This simulates an insert in s or a delete in t.
• Step 5: If all previous characters match, the only way the strings are one edit apart is if t has one extra character at the end.

This approach only requires a single pass through the strings and uses constant extra space.

Example Walkthrough

Consider s = "cat" and t = "cats":

• Lengths: m = 3, n = 4. n - m = 1, so possible one edit.
• Compare characters:
  • s[0] == t[0] ('c' == 'c')
  • s[1] == t[1] ('a' == 'a')
  • s[2] == t[2] ('t' == 't')
• No mismatches found. Since t is longer by one character, and all previous characters matched, the only difference is the last character 's' in t.
• Thus, s and t are one edit distance apart (insertion at the end).

Now, consider s = "cat" and t = "cut":

• Lengths are equal.
• Compare characters:
  • s[0] == t[0] ('c' == 'c')
  • s[1] != t[1] ('a' != 'u')
• Check if s[2:] == t[2:] ('t' == 't'). Yes.
• This means a single replace operation at index 1 turns "cat" into "cut".

Time and Space Complexity

• Brute-force approach: Generating all one-edit variations of s and comparing to t is O(N²), where N is the length of the string, because for each position you could insert, delete, or replace a character, and each operation requires copying the string.
• Optimized approach (above): The solution compares the strings in a single pass, so the time complexity is O(N), where N is the length of the shorter string. Only a constant amount of extra space is used, aside from the input strings, so space complexity is O(1).

Summary

The "One Edit Distance" problem is efficiently solved by comparing the two strings character by character and handling the three possible edit operations (insert, delete, replace) in a unified way. By always treating the shorter string as s and checking for a single difference, the solution avoids unnecessary computation and achieves linear time with constant space. The approach is elegant because it reduces the problem to a simple scan and comparison, making it both intuitive and performant.