One Edit Distance

Question:

Given two strings S and T, determine if they are both one edit distance apart.

Hint:

1. If | n – m | is greater than 1, we know immediately both are not one-edit distance apart.

2. It might help if you consider these cases separately, m == n and m ≠ n.

3. Assume that m is always ≤ n, which greatly simplifies the conditional statements.

If m > n, we could just simply swap S and T.

4. If m == n, it becomes finding if there is exactly one modified operation. If m ≠ n, you do not have to consider the delete operation. Just consider the insert operation in T.

Solution:

O(n) runtime, O(1) space – Simple one-pass:

For the case where m is equal to n, it becomes finding if there is exactly one modified

character. 

Now let’s assume m ≤ n. (If m > n we could just swap them).

Assume X represents the one-edit character. There are three one-edit distance operations

that could be applied to S.

i. Modify operation – Modify a character to X in S.

    S = “abcde” T = “abXde”

ii. Insert operation – X was inserted before a character in S.

    S = “abcde” T = “abcXde”

iii. Append operation – X was appended at the end of S.

    S = “abcde” T = “abcdeX”

First pass over S and T concurrently and stop at the first non-matching character between S and T.

1. If S matches all characters in T, then check if there is an extra character at the end of T. (Append operation)

2. If | n – m | == 1, that means we must skip this non-matching character only in T and make sure the remaining characters between S and T are exactly matching. (Insert operation)

3. If | n – m | == 0, then we skip both non-matching characters in S and T and make sure the remaining characters between S and T are exactly matching. (Modify operation)

public static 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;
  
  int i = 0, diff = n - m;
  while(i < m && s.charAt(i) == t.charAt(i)) {
   i++;
  }
  
  //if s matches all characters in t
  //Append: check if there is an extra character at the end of T.
  if(i == m && diff > 0)
   return true;
  
  //if |m - n|=0
  //Modify: skip both non-matching characters in S and T and make sure the remaining characters are matching
  if(diff == 0)
   i++;
  
  //if |m - n|=1
  //Insert: skip this non-matching character only in T and make sure the remaining characters are matching
  while(i < m && s.charAt(i) == t.charAt(i + diff)) {
   i++;
  }
  
  if(i == m)
   return true;
  
  return false;
 }