161. One Edit Distance

Problem:

---

Given two strings s and t, determine if they are both one edit distance apart.

Note: 

There are 3 possiblities to satisify one edit distance apart:

1. Insert a character into s to get t
2. Delete a character from s to get t
3. Replace a character of s to get t

Example 1:

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

Example 2:

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

Example 3:

Input: s = "1203", t = "1213"
Output: true
Explanation: We can replace '0' with '1' to get t.

Analysis:

8/3/2018 update:
这一次用的方法非常屌。在循环内不用考虑长度大小问题，循环肯定按照长度小的来。和Median of Two sorted array一样，用递归解决。刷题功力又上一层了。

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16

class Solution { public boolean isOneEditDistance(String s, String t) { if (s == null || t == null) return false; int slen = s.length(), tlen = t.length(); if (slen > tlen) return isOneEditDistance(t, s); for (int i = 0; i < slen; i++) { if (s.charAt(i) != t.charAt(i)) { return s.substring(i).equals(t.substring(i + 1)) || t.substring(i + 1).equals(s.substring(i + 1)); } } return tlen - slen == 1; } }

5/21/2018 update:
A better implementation

class Solution {
    public boolean isOneEditDistance(String s, String t) {
        int m = s.length();
        int n = t.length();
        
        for (int i = 0; i < Math.min(m, n); i++) {
            if (s.charAt(i) != t.charAt(i)) {
                if (m == n) 
                    return s.substring(i + 1).equals(t.substring(i + 1));
                if (m > n) 
                    return s.substring(i + 1).equals(t.substring(i));
                else
                    return t.substring(i + 1).equals(s.substring(i));    
            }
            
        }
        return Math.abs(m - n) == 1;
    }
}

The idea is to find the first occurrence of chars which are not equal.
1. m  == n, replace.
   abc de
   abf de
   012
   c and f are not equal. We want to know if the part of S and T after pos 2 are equal or not.
2. m > n, delete or insert
   abcde
   abde
   012
   c and d are not equal. Then we compare s.substring(3) and t.substring(2).
3. n < m, delete or insert. Same thing as 2.

There is on case left behind, abc and ab. The diff char is at end of string. So we need to make sure the diff of length is exact 1. 
--------------------------------------------------------------------------------------------------------------------------------------------


One edit distance are insert, modify and delete. Delete is equivalent to insert, 1 char diff. m and n are length of S and T respectively. 

1. |m-n| > 1 false

2. m == n, check there is only one char diff in S and T.

3. |m - n| == 1, delete or insert 1, take the diff char out and compare rest. 

m > n is compared by default, n > m can be achieved by swapping S and T.

Solution:

 class Solution {  
   public boolean isOneEditDistance(String s, String t) {  
     int m = s.length();  
     int n = t.length();  
     if (Math.abs(m - n) > 1) return false;  
     if (m == n) return isOneModify(s, t);  
     if (m - n == 1) return isOneDelete(s, t);  
     return isOneDelete(t, s);  
   }  
   // s.length() > t.length()  
   private boolean isOneDelete(String s, String t) {  
     for (int i = 0, j = 0; j < t.length(); i++, j++) {  
       if (s.charAt(i) != t.charAt(j))   
         return s.substring(i+1).equals(t.substring(j)) ;  
     }  
     return true;  
   }  
   private boolean isOneModify(String s, String t) {  
     int diff = 0;  
     for (int i = 0; i < t.length(); i++) {  
       if (s.charAt(i) != t.charAt(i) )   
         diff++;  
     }  
     return diff == 1;  
   }  
 }