package com.freetymekiyan.algorithms.level.medium;

/**
 * Given two strings S and T, determine if they are both one edit distance apart.
 * <p>
 * Company Tags: Snapchat, Uber, Facebook, Twitter
 * Tags: String
 * Similar Problems: (H) Edit Distance
 */
public class OneEditDistance {

    /**
     * Edit distance: add, remove, or replace.
     * Three possible situations:
     * 1) s and t are of same length, replace
     * 2) delete 1 char from s
     * 3) delete 1 char from t
     * <p>
     * Implementation:
     * Get the lengths of two strings, m and n.
     * Compare m and n. Always put the shorter string as the first parameter.
     * If the difference of their lengths are larger than 1, return false.
     * Loop through the shorter string to find a different char.
     * If found and they are of same length, the rest of them should be the same.
     * If found and they are of different length, the rest of shorter string, including that char,
     * should be the same as the rest of longer string, excluding that char.
     * If all chars are the same, it can only be the last character in longer string.
     * Return true iff longer string is one character longer.
     */
    public boolean isOneEditDistance(String s, String t) {
        int m = s.length();
        int n = t.length();
        if (m > n) {
            return isOneEditDistance(t, s); // This way, n >= m always
        }
        if (n - m > 1) return false;
        for (int i = 0; i < m; i++) {
            if (s.charAt(i) == t.charAt(i)) {
                continue;
            }
            if (m == n) {
                return s.substring(i + 1).equals(t.substring(i + 1));
            }
            if (m < n) {
                return s.substring(i).equals(t.substring(i + 1));
            }
        }
        return m != n; // If all characters are the same, will pass previous checks.
    }
}

@@ -49,16 +49,49 @@
 m;%0A%0A/**%0A
+ * 163. One Edit Distance%0A * %3Cp%3E%0A
  * Given
@@ -1411,31 +1411,27 @@
  // 
-This way, n %3E= m always
+Short length first.
 %0A   
@@ -1473,16 +1473,62 @@
 n false;
+ // Pruning. Can't be over 1 letter different.
 %0A       
@@ -1586,17 +1586,17 @@
 arAt(i) 
-=
+!
 = t.char
@@ -1612,44 +1612,8 @@
     
-            continue;%0A            %7D%0A
     
@@ -1642,32 +1642,36 @@
                 
+ 
+   
 return s.substri
@@ -1724,21 +1724,18 @@
     
-%7D%0A
     
-       
+%7D else
  if 
@@ -1752,32 +1752,36 @@
                 
+   
+ 
 return s.substri
@@ -1806,32 +1806,50 @@
 string(i + 1));%0A
+                %7D%0A
             %7D%0A  
@@ -1948,9 +1948,8 @@
 %0A    %7D%0A%7D
-%0A

update 163. One Edit Distance