LeetCode 161 - One Edit Distance

Related: LeetCode Edit Distance
Extended: follow-up 问如果输入不是两个string, 而是char stream怎么办? 这样子就不能用length 来比较了
[LeetCode] One Edit Distance | 程序员达达
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.

https://discuss.leetcode.com/topic/30308/my-clear-java-solution-with-explanation

/*
 * There're 3 possibilities to satisfy one edit distance apart: 
 * 
 * 1) Replace 1 char:
    s: a B c
    t: a D c
 * 2) Delete 1 char from s: 
   s: a D  b c
   t: a    b c
 * 3) Delete 1 char from t
   s: a   b c
   t: a D b c
 */
public boolean isOneEditDistance(String s, String t) {
    for (int i = 0; i < Math.min(s.length(), t.length()); i++) { 
     if (s.charAt(i) != t.charAt(i)) {
      if (s.length() == t.length()) // s has the same length as t, so the only possibility is replacing one char in s and t
       return s.substring(i + 1).equals(t.substring(i + 1));
   else if (s.length() < t.length()) // t is longer than s, so the only possibility is deleting one char from t
    return s.substring(i).equals(t.substring(i + 1));          
   else // s is longer than t, so the only possibility is deleting one char from s
    return t.substring(i).equals(s.substring(i + 1));
     }
    }       
    //All previous chars are the same, the only possibility is deleting the end char in the longer one of s and t 
    return Math.abs(s.length() - t.length()) == 1;        
}

Very smart! It's much clear to figure out how to handle when we find the first different char.

    public boolean isOneEditDistance(String s, String t) {
        int m = s.length(), n = t.length();
        if (Math.abs(m - n) > 1) return false;
        for (int i = 0; i < Math.min(m, n); 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 + 1).equals(t.substring(i));
            else return s.substring(i).equals(t.substring(i + 1));
        } //return Math.abs(s.length() - t.length()) == 1;  
        return m != n; /* Only last char different. eg."abcd" "abc". Rule out equal case "abc" "abc" */
    }

http://segmentfault.com/a/1190000003906621

虽然我们可以用Edit Distance的解法，看distance是否为1，但Leetcode中会超时。这里我们可以利用只有一个不同的特点在O(N)时间内完成。如果两个字符串只有一个编辑距离，则只有两种情况：

1. 两个字符串一样长的时候，说明有一个替换操作，我们只要看对应位置是不是只有一个字符不一样就行了
2. 一个字符串比另一个长1，说明有个增加或删除操作，我们就找到第一个对应位置不一样的那个字符，如果较长字符串在那个字符之后的部分和较短字符串那个字符及之后的部分是一样的，则符合要求
3. 如果两个字符串长度差距大于1，肯定不对

    public boolean isOneEditDistance(String s, String t) {
        int m = s.length(), n = t.length();
        if(m == n) return isOneModified(s, t);
        if(m - n == 1) return isOneDeleted(s, t);
        if(n - m == 1) return isOneDeleted(t, s);
        // 长度差距大于2直接返回false
        return false;
    }
    
    private boolean isOneModified(String s, String t){
        boolean modified = false;
        // 看是否只修改了一个字符
        for(int i = 0; i < s.length(); i++){
            if(s.charAt(i) != t.charAt(i)){
                if(modified) return false;
                modified = true;
            }
        }
        return modified;
    }
    
    public boolean isOneDeleted(String longer, String shorter){
        // 找到第一组不一样的字符，看后面是否一样
        for(int i = 0; i < shorter.length(); i++){
            if(longer.charAt(i) != shorter.charAt(i)){
                return longer.substring(i + 1).equals(shorter.substring(i));
            }
        }
        return true;
    }

http://codeanalysis111.blogspot.com/2014/12/one-edit-distance.html
     public boolean isOneEditDistance(String s, String t) {
        if(Math.abs(s.length() - t.length()) > 1) return false;
        if(s.length() == t.length()) return isOneSameLength(s, t);
        if(s.length() > t.length()) return isOneDifLength(t, s);
        else return isOneDifLength(s, t);
    }
    private boolean isOneDifLength(String s, String l) {
         int i = 0;
        while(i < s.length() && s.charAt(i) == l.charAt(i)) {++i;}
        if(i == s.length()) return true;
        return s.substring(i).equals(l.substring(i + 1));
    }
    private boolean isOneSameLength(String s, String t) {
        int dif = 0;
        for(int i = 0; i < s.length(); ++i) {
             if(s.charAt(i) != t.charAt(i)) ++dif;
             if(diff>1) return false; // exit early
        }
        return dif == 1;
    }
http://blog.csdn.net/chibaoneliuliuni/article/details/46969869

1.     public boolean isOneEditDistance(String s, String t) {  
2.         // make s to be the shorter String  
3.         if(s.length() > t.length()){  
4.             return isOneEditDistance(t, s);  
5.         }  
6.           
7.         if(t.length() - s.length() > 1){  
8.             return false;  
9.         }          
10.         int shift = t.length() - s.length();  
11.         int i = 0;  
12.         while(i < s.length() && s.charAt(i) == t.charAt(i)){  
13.             i++;  
14.         }  
15.         if(shift == 0){  
16.             i++;  
17.             while(i < s.length() && s.charAt(i) == t.charAt(i)){  
18.                 i++;  
19.             }  
20.             return i == s.length();  
21.         }else{  
22.             while(i < s.length() && s.charAt(i) == t.charAt(i + 1)){  
23.                 i++;  
24.             }  
25.             return i == s.length();  
26.         }  
27.     } 

https://tonycao.gitbooks.io/leetcode-locked/content/LeetCode%20Locked/c1.9.html

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.

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

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

S = “abcde” T = “abXde”
S = “abcde” T = “abcXde”
S = “abcde” T = “abcdeX”

We make a 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. (Modify 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. (Append operation)

public 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, shift = n - m;
   while (i < m && s.charAt(i) == t.charAt(i)) i++;
   if (i == m) return shift > 0;
   if (shift == 0) i++;
   while (i < m && s.charAt(i) == t.charAt(i + shift)) i++;
   return i == m;
}

Different solution:
https://leetcode.com/discuss/61772/simple-java-solution
public boolean isOneEditDistance(String s, String t) { if(Math.abs(s.length() - t.length()) > 1) return false; int i = 0, j = 0,err = 0; while(i<s.length() && j<t.length()) { if(s.charAt(i) != t.charAt(j)) { err++; if(err > 1) return false; if(s.length() > t.length()) j--; else if(s.length() < t.length()) i--; } i++; j++; } return (err == 1 || (err == 0 && t.length() != s.length()))? true: false; }
https://leetcode.com/discuss/64603/java-very-simple-w-explanation
public boolean isOneEditDistance(String s, String t) { if (Math.abs(s.length() - t.length()) > 1) { return false; } int diff = s.length() - t.length(); String longer = diff > 0 ? s : t; // potentially longer string String shorter = diff > 0 ? t : s; // potentially shorter string for (int i = 0; i < shorter.length(); i++) { if (longer.charAt(i) != shorter.charAt(i)) { // we allow only one mismatch, afterwards the substrings should match if (diff == 0) { // strings are equal in length, they are only 1 edit distance // apart if substrings cut after index i are equal // ....a[xyz] // ....b[xyz] String longerSubstr = longer.substring(i + 1, longer.length()); String shorterSubstr = shorter.substring(i + 1, shorter.length()); return longerSubstr.equals(shorterSubstr); } else { // longer string is actually longer, substring cut after i should // match substring cut at i on the shorter string // ....a[xyz] // ....[xyz] String longerSubstr = longer.substring(i + 1, longer.length()); String shorterSubstr = shorter.substring(i, shorter.length()); return longerSubstr.equals(shorterSubstr); } } } // at this point we know the potentially longer string matches all of the // potentially shorter string. Only case when this is still one edit distance // apart is if the potentially longer string is actually longer. return diff != 0; }
https://leetcode.com/discuss/71071/my-clear-java-solution-with-explanation
public boolean isOneEditDistance(String s, String t) { for (int i = 0; i < Math.min(s.length(), t.length()); i++) { if (s.charAt(i) != t.charAt(i)) { if (s.length() == t.length()) // s has the same length as t, so the only possibility is replacing one char in s and t return s.substring(i + 1).equals(t.substring(i + 1)); else if (s.length() < t.length()) // t is longer than s, so the only possibility is deleting one char from t return s.substring(i).equals(t.substring(i + 1)); else // s is longer than t, so the only possibility is deleting one char from s return t.substring(i).equals(s.substring(i + 1)); } } //All previous chars are the same, the only possibility is deleting the end char in the longer one of s and t return Math.abs(s.length() - t.length()) == 1; }
https://leetcode.com/discuss/44971/accepted-clean-java-solution-with-explanation-two-pointers
public boolean isOneEditDistance(String s, String t) { if (s == null || t == null) return false; if (s.length() > t.length()) return isOneEditDistance(t, s); int i = 0, j = 0; while (i < s.length() && j < t.length()) { if (s.charAt(i) != t.charAt(j)) { // we try to replace s[i] with s[j] or insert s[j] to s[i] // then compare the rest and see if they are the same return s.substring(i + 1).equals(t.substring(j + 1)) || s.substring(i).equals(t.substring(j + 1)); } i++; j++; } return t.length() - j == 1; }

public boolean isOneEditDistance(String s, String t) { int s_len = s.length(); int t_len = t.length(); if (t_len < s_len) return isOneEditDistance(t, s); if (t_len - s_len > 1) return false; int i = 0; while (i < s_len) { if (s.charAt(i) != t.charAt(i)) return s.substring(i+1).equals(t.substring(i+1)) || s.substring(i).equals(t.substring(i+1)); i++; } return s_len + 1 == t_len; }
https://leetcode.com/discuss/44971/accepted-clean-java-solution-with-explanation-two-pointers
t I think we have no need to maintain index j on String t, since i and j are always in the in the same pace until we return
https://leetcode.com/discuss/54087/easy-understood-java-solution
public boolean isOneEditDistance(String s, String t) { if(Math.abs(s.length()-t.length()) > 1) return false; if(s.length() == t.length()) return isOneModify(s,t); if(s.length() > t.length()) return isOneDel(s,t); return isOneDel(t,s); } public boolean isOneDel(String s,String t){ for(int i=0,j=0;i<s.length() && j<t.length();i++,j++){ if(s.charAt(i) != t.charAt(j)){ return s.substring(i+1).equals(t.substring(j)); } } return true; } public boolean isOneModify(String s,String t){ int diff =0; for(int i=0;i<s.length();i++){ if(s.charAt(i) != t.charAt(i)) diff++; } return diff==1; }
https://leetcode.com/discuss/20038/my-solutions-in-3-languages-with-one-for-loop
for (int i = 0; i < Math.min(s.length(), t.length()); i++) { if (s.charAt(i) != t.charAt(i)) { return s.substring(i + (s.length() >= t.length() ? 1 : 0))
.equals(t.substring(i + (s.length() <= t.length() ? 1 : 0))); } } return Math.abs(s.length() - t.length()) == 1;
https://github.com/mission-peace/interview/blob/master/src/com/interview/recursion/OneEditApart.java
    public boolean matchIterative(char str1[], char str2[]){
        if(str1.length < str2.length){
            char temp[] = str1;
            str1 = str2;
            str2 = temp;
        }
     
        if(str1.length - str2.length > 1){
            return false;
        }
        int k = 1;
        if(str1.length == str2.length){
            int i =0;
            int j =0;
            while(k >= 0 && i < str1.length){
                if(str1[i] != str2[j]){
                    k--;
                }
                i++;
                j++;
            }
            if(k < 0){ // k!=0 depend on the question
                return false;
            }
        }else{
            int i=0;
            int j =0;
            while(k >= 0 && i < str1.length && j < str2.length){
                if(str1[i] != str2[j]){
                    i++;
                    k--;
                    continue;
                }
                i++;
                j++;
            }
            if(k == -1){
                return false;
            }
        }
        return true;
    }
http://www.geeksforgeeks.org/check-if-two-given-strings-are-at-edit-distance-one/

An Efficient Solution is to simultaneously traverse both strings and keep track of count of different characters. Below is complete algorithm.

Let the input strings be s1 and s2 and lengths of input 
strings be m and n respectively.

1) If difference between m an n is more than 1, 
     return false.
2) Initialize count of edits as 1.
3) Start traversing both strings from first character.
    a) If current characters don't match, then
       (i)   Increment count of edits
       (ii)  If count becomes more than 1, return false
       (iii) If length of one string is more, then only
             possible  edit is to remove a character.
             Therefore, move ahead in larger string.
       (iv)  If length is same, then only possible edit
             is to  change a character. Therefore, move
             ahead in both strings. 
    b) Else, move ahead in both strings. 

// Returns true if edit distance between s1 and

// s2 is one, else false

bool isEditDistanceOne(string s1, string s2)

{

    // Find lengths of given strings

    int m = s1.length(), n = s2.length();

    // If difference between lengths is more than

    // 1, then strings can't be at one distance

    if (abs(m - n) > 1)

        return false;

    int count = 0; // Count of edits

    int i = 0, j = 0;

    while (i < m && j < n)

    {

        // If current characters don't match

        if (s1[i] != s2[j])

        {

            if (count == 1)

                return false;

            // If length of one string is

            // more, then only possible edit

            // is to remove a character

            if (m > n)

                i++;

            else if (m< n)

                j++;

            else //Iflengths of both strings is same

            {

                i++;

                j++;

            }

             

            // Increment count of edits

            count++;

        }

        else // If current characters match

        {

            i++;

            j++;

        }

    }

    // If last character is extra in any string

    if (i < m || j < n)

        count++;

    return count == 1;

}

A Simple Solution is to find Edit Distance using Dynamic programming. If distance is 1, then return true, else return false. Time complexity of this solution is O(n2)

https://github.com/careercup/CtCI-6th-Edition/tree/master/Java/Ch%2001.%20Arrays%20and%20Strings/Q1_05_One_Away
public static boolean oneEditReplace(String s1, String s2) {
boolean foundDifference = false;
for (int i = 0; i < s1.length(); i++) {
if (s1.charAt(i) != s2.charAt(i)) {
if (foundDifference) {
return false;
}

foundDifference = true;
}
}
return true;
}

/* Check if you can insert a character into s1 to make s2. */
public static boolean oneEditInsert(String s1, String s2) {
int index1 = 0;
int index2 = 0;
while (index2 < s2.length() && index1 < s1.length()) {
if (s1.charAt(index1) != s2.charAt(index2)) {
if (index1 != index2) {
return false;
}
index2++;
} else {
index1++;
index2++;
}
}
return true;
}

public static boolean oneEditAway(String first, String second) {
if (first.length() == second.length()) {
return oneEditReplace(first, second);
} else if (first.length() + 1 == second.length()) {
return oneEditInsert(first, second);
} else if (first.length() - 1 == second.length()) {
return oneEditInsert(second, first);
}
return false;
}

https://github.com/careercup/CtCI-6th-Edition/blob/master/Java/Ch%2001.%20Arrays%20and%20Strings/Q1_05_One_Away/QuestionB.java

public static boolean oneEditAway(String first, String second) {
/* Length checks. */
if (Math.abs(first.length() - second.length()) > 1) {
return false;
}

/* Get shorter and longer string.*/
String s1 = first.length() < second.length() ? first : second;
String s2 = first.length() < second.length() ? second : first;

int index1 = 0;
int index2 = 0;
boolean foundDifference = false;
while (index2 < s2.length() && index1 < s1.length()) {
if (s1.charAt(index1) != s2.charAt(index2)) {
/* Ensure that this is the first difference found.*/
if (foundDifference) return false;
foundDifference = true;
if (s1.length() == s2.length()) { // On replace, move shorter pointer
index1++;
}
} else {
index1++; // If matching, move shorter pointer
}
index2++; // Always move pointer for longer string
}
return true;
}


Follow-up
Facebook isDistanceZeroOrOne
https://discuss.leetcode.com/topic/25774/c-solution-for-stream-file-where-you-don-t-know-the-length-of-the-strings
If it is a file or stream where you have iterator only moves forward, and you only know the size when you hit the end, we have to split into 3 cases when first difference occurs.
I use s.size() and t.size() in the code but they can be easily translated into iter!=s.end()
Stream processing is much harder for this problem as we cannot compare the length of two strings.

bool isOneEditDistance(string s, string t) {
    int i =0;
    while(i<s.size() && i<t.size() && s[i]==t[i]){
         ++i;
    }
    
    if(i==s.size() && i==t.size()) return false;
    else if(i==s.size() && i+1==t.size() || i==t.size() && i+1==s.size()) return true;
    else if(i<s.size() && i<t.size()){
        ++i;
        bool s1=true, s2=true, s3=true;//3 senarios
        while(i<s.size() && i<t.size()){
          if(s[i]!=t[i-1]) s1=false;
          if(s[i]!=t[i]) s2=false;
          if(s[i-1]!=t[i]) s3=false;
          if(!s1 && !s2 && !s3) return false;
          ++i;
        }
        if(s1 && i+1==s.size() && s[i]==t[i-1]) return true;
        if(s2 && i==s.size() && i==t.size()) return true;
        if(s3 && i+1==t.size() && s[i-1]==t[i]) return true;
        return false;
    }
}

Read full article from [LeetCode] One Edit Distance | 程序员达达