[Algorithm] One Edit Apart

Given two strings, return boolean True/False, if they are only one edit apart.Edit can be insert/delete/update of only one character in the string.

For example:
-True
xyz,xz
xyz, xyk
xy, xyz


-False
xyz, xyz
xyz,xzy 
x, xyz 

This problem is quite similar with edit distance. We could use the same code to calculate the minimum edit distance to change str1 to str2, and check if it is equal to one or not. However, we could use much simple code with O(n) time complexity. The core idea is that there is only one edit. So we could have several discussions (we assume str1 is the longer string):

1. The difference of length is greater than 2, at least 2 edit distance, we could directly return false;
2. The length are equal, there must be one and only one character differs, O(n) time to check;
3. The length is differ by one, str1 must have one more character than str2. From the head of str2, check each character with str1, if at i we find there is a different character, we compare the str2(i, ...,end) with str1(i+1, ..., end) to see if there is only one character less and all others are the same;

import java.util.*;

public class OneEditApart {
 public static boolean match(String str1, String str2) {
  if(str1.length() < str2.length()) {
   String temp = str2;
   str2 = str1;
   str1 = temp;
  } // always assume str1 is longer than str2
  
  // length differ more than 2 would not match
  if(str1.length() - str2.length() >= 2)
   return false;
  // length equal then must have one and only one character differ
  else if(str1.length() == str2.length()) {
   for(int i = 0; i < str1.length(); i++) {
    if(str1.charAt(i) != str2.charAt(i)) 
     return str1.substring(i+1).equals(str2.substring(i+1));
   }
   return false;
  }
  // length is differ by one, str1 must have one character more than str2
  else {
   for(int i = 0; i < str2.length(); i++) {
    if(str1.charAt(i) != str2.charAt(i)) 
     return str1.substring(i+1).equals(str2.substring(i));
   }
   return true;
  }
 }
 
 public static void main(String[] args) {
  Scanner scan = new Scanner(System.in);
  while(scan.hasNext()) {
   String str1 = scan.next();
   String str2 = scan.next();
   System.out.println(match(str1, str2));
  }
 }
}