/**
 * Created by kiyan on 5/5/16.
 */
public class OneEditDistance {

    public boolean isOneEditDistance(String s, String t) {
        int m = s.length();
        int n = t.length();
        if (m > n) return isOneEditDistance(t, s); // n is always bigger
        if (n - m > 1) return false;
        int i = 0;
        int shift = n - m; // 0 or 1
        while (i < m && s.charAt(i) == t.charAt(i)) i++; // arrives at non-matching char
        if (i == m) return shift > 0; // whether T has more characters
        if (shift == 0) i++; // skip both
        while (i < m && s.charAt(i) == t.charAt(i + shift)) i++; // go on
        return i == m; // should reach the end of shorter string
    }
}

@@ -1,74 +1,1041 @@
-/**%0A * Created by kiyan on 5/5/16.%0A */%0Apublic class OneEditDistance %7B%0A
+package com.freetymekiyan.algorithms.level.medium;%0A%0A/**%0A * Given two strings S and T, determine if they are both one edit distance apart.%0A * %3Cp%3E%0A * Company Tags: Snapchat, Uber, Facebook, Twitter%0A * Tags: String%0A * Similar Problems: (H) Edit Distance%0A */%0Apublic class OneEditDistance %7B%0A%0A    /**%0A     * Edit distance: add, remove, or replace.%0A     * Three possible situations:%0A     * 1) s and t are of same length, replace%0A     * 2) delete 1 char from s%0A     * 3) delete 1 char from t%0A     * If the difference of their lengths are larger than 1, return false.%0A     * Loop through the shorter string to find a different char.%0A     * If found and they are of same length, the rest of them should be the same.%0A     * If found and they are of different length, the rest of shorter string, including that char,%0A     * should be the same as the rest of longer string, excluding that char.%0A     * If all chars are the same, it can only be the last character in longer string.%0A     * Return true iff longer string is one character longer.%0A     */
 %0A   
@@ -1164,16 +1164,30 @@
  (m %3E n)
+ %7B%0A           
  return 
@@ -1213,16 +1213,26 @@
 , s); //
+ This way,
  n is al
@@ -1242,16 +1242,23 @@
 s bigger
+ than m
 %0A       
@@ -1262,45 +1262,23 @@
     
-if (n - m %3E 1) return false;%0A
+%7D%0A 
        
- 
+for (
 int 
@@ -1287,143 +1287,118 @@
 = 0;
-%0A        int shift = n - m; // 0 or 1%0A        while (i %3C m && s.charAt(i) == t.charAt(i)) i++; // arrives at non-matching char%0A
+ i %3C m; i++) %7B%0A            if (s.charAt(i) == t.charAt(i)) %7B%0A                continue;%0A            %7D%0A 
         
 if (
@@ -1397,186 +1397,223 @@
     
+   
 if (
-i
+m
  == 
-m) return shift %3E 0; // whether T has more characters%0A        if (shift == 0) i++; // skip both%0A        while (i %3C m && s.charAt(i) == t.charAt(i + shift)) i++; // go on
+n) %7B%0A                return s.substring(i + 1).equals(t.substring(i + 1));%0A            %7D%0A            if (m %3C n) %7B%0A                return s.substring(i).equals(t.substring(i + 1));%0A            %7D%0A        %7D
 %0A   
@@ -1628,57 +1628,54 @@
 urn 
-i
+m
  == 
-m; // should reach the end of shorter string
+n - 1; // All previous chars are the same
 %0A   

update one edit distance