Problem

Given two strings s and t, return true if they are both one edit distance apart, otherwise return false.

A string s is said to be one distance apart from a string t if you can:

  • Insert exactly one character into s to get t.
  • Delete exactly one character from s to get t.
  • Replace exactly one character of s with a different character to get t.

OR

Another way to put the problem Two words are friends if they have a Levenshtein distance of 1. That is, you can add, remove, or substitute exactly one letter in word X to create word Y. A word’s social network consists of all of its friends, plus all of their friends, and all of their friends’ friends, and so on. Write a program to tell us how big the social network for the word “causes” is, using this word list. Have fun!

Examples

Example 1:

1
2
3

Input: s = "ab", t = "acb"
Output: true
Explanation: We can insert 'c' into s to get t.

Example 2:

1
2
3

Input: s = "", t = ""
Output: false
Explanation: We cannot get t from s by only one step.

Solution

Method 1 - Iteration

To determine if two strings are one edit distance apart, consider the three allowed operations:

  1. Insertion
  2. Deletion
  3. Replacement

Steps

  1. Length Check:
    • If the absolute difference in their lengths is greater than 1, they can’t be one edit distance apart.
  2. Iteration and Comparison:
    • Iterate through both strings simultaneously.
    • Compare characters at each position.
    • If characters differ, check for the possible operations:
      • Insertion/Deletion: If the lengths are different, shift the pointer of the longer string.
      • Replacement: If the lengths are the same, shift both pointers.
    • If more than one difference is found, return false.
  3. Edge Cases:
    • Consider edge cases where the strings differ exactly by one character in length (requires appending the last character).

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

class Solution {
    public boolean isOneEditDistance(String s, String t) {
        int lenS = s.length();
        int lenT = t.length();
        
        // If length difference is greater than 1, they can't be one edit distance apart
        if (Math.abs(lenS - lenT) > 1) {
            return false;
        }
        
        // Identify the shorter and longer string
        String shorter = lenS < lenT ? s : t;
        String longer = lenS < lenT ? t : s;
        
        boolean foundDifference = false;
        for (int i = 0, j = 0; i < shorter.length(); i++, j++) {
            if (shorter.charAt(i) != longer.charAt(j)) {
                if (foundDifference) {
                    return false; // More than one edit
                }
                foundDifference = true;
                
                if (lenS != lenT) {
                    i--; // Offset index for the shorter string
                }
            }
        }
        
        // If no differences found but lengths differ by one, it's one edit
        return foundDifference || lenS + 1 == lenT;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

class Solution:
    def is_one_edit_distance(self, s: str, t: str) -> bool:
        len_s, len_t = len(s), len(t)
        
        # If length difference is greater than 1, they can't be one edit distance apart
        if abs(len_s - len_t) > 1:
            return False
        
        found_difference = False
        i, j = 0, 0
        
        while i < len(s) and j < len(t):
            if s[i] != t[j]:
                if found_difference:
                    return False  # More than one edit
                found_difference = True
                
                if len_s > len_t:
                    j -= 1  # Offset for deletion
                elif len_s < len_t:
                    i -= 1  # Offset for insertion
                
            i += 1
            j += 1
        
        # If no differences found but lengths differ by one, it's one edit
        return found_difference or len_s + 1 == len_t

Complexity

  • ⏰ Time complexity: O(n) where n is the length of the shorter string min(len(s), len(t)). The entire string is traversed once.
  • 🧺 Space complexity: O(1) as we use a constant amount of extra space.