Massive Algorithms: Facebook isDistanceZeroOrOne

Facebook isDistanceZeroOrOne | Moonstone

LeetCode 161 - One Edit Distance
isDistanceZeroOrOne | Moonstone
class IntFileIterator {
boolean hasNext();
int next();
}
class{
public boolean isDistanceZeroOrOne(IntFileIterator a, IntFileIterator b)；
}
// return if the distance between a and b is at most 1..
// Distance: minimum number of modifications to make a=b
// Modification:
// 1. change an int in a
// 2. insert an int to a
// 3. remove an int from a
这题就是one edit distance的变形题，难点在于给的Iterator，事先不知道两个file
的长度，也不允许用extra space（所以不能转成两个string再比），那么一个个往前
跑的时候就得三种情况都考虑。。。。
X.
http://shanhe.me/2015/03/20/check-if-two-integer-iterators-have-the-maximum-distance-of-one

  static boolean isDistanceZeroOrOne(IntIterator a, IntIterator b) {

```
    boolean trying = false;
```
```
    boolean changable = false;
```
```
    boolean insertable = false;
```
```
    boolean removable = false;
```

    for(int aPrevious = 0, bPrevious = 0, aCurrent = 0, bCurrent = 0;

        ; aPrevious = aCurrent, bPrevious = bCurrent) {

```
      if(a.hasNext()) {
```
```
        aCurrent = a.next();
```

        if(b.hasNext()) { // a != null, b != null.

```
          bCurrent = b.next();
```
```
          if(trying) {
```
```
            if(changable) {
```

              if(aCurrent != bCurrent) {

```
                changable = false;
```
```
              }
```
```
            }
```
```
            if(insertable) {
```

              if(bCurrent != aPrevious) {

```
                insertable = false;
```
```
              }
```
```
            }
```
```
            if(removable) {
```

              if(aCurrent != bPrevious) {

```
                removable = false;
```
```
              }
```
```
            }
```

            if(!changable && !insertable && !removable) {

```
              return false;
```
```
            }
```

          } else if(aCurrent != bCurrent) {

            // start trying all the possibilities.

```
            trying = true;
```
```
            changable = true;
```
```
            insertable = true;
```
```
            removable = true;
```
```
          }
```

        } else { // a != null, b == null.

```
          if(trying) {
```

            if(removable && aCurrent == bPrevious) {

```
              return !a.hasNext();
```
```
            } else {
```
```
              return false;
```
```
            }
```
```
          } else { // remove a.
```
```
            return !a.hasNext();
```
```
          }
```
```
        }
```
```
      } else {
```

        if(b.hasNext()) { // a == null, b != null.

```
          bCurrent = b.next();
```
```
          if(trying) {
```

            if(insertable && bCurrent == aPrevious) {

```
              return !b.hasNext();
```
```
            } else {
```
```
              return false;
```
```
            }
```
```
          } else { // insert b.
```
```
            return !b.hasNext();
```
```
          }
```

        } else { // a == null, b == null.

          // can only fulfill changable if we are trying.

          return trying ? (changable ? true : false) : true;

```
        }
```
```
      }
```
```
    }
```
```
  }
```

http://www.meetqun.net/thread-11316-1-1.html
http://coderchen.blogspot.com/2015/10/zerooroneeditdistance-with-iterator-as.html

public static boolean isOneEditDistance(Iterator<Character> a, Iterator<Character> b) {
boolean isSame = true, isChanged = false, isAdd = false, isRemove = false;
int prevA = 0, prevB = 0, curA = 0, curB = 0;
while (a.hasNext() && b.hasNext()) {
prevA = curA;
prevB = curB;
curA = a.next();
curB = b.next();
if (isSame) {
if (curA != curB) {
isSame = false;
isChanged = true;
isAdd = true;
isRemove = true;
}
} else {
if (isChanged) {
if (curA != curB) {
isChanged = false;
}
}
if (isAdd) {
if (prevA != curB) {
isAdd = false;
}
}
if (isRemove) {
if (curA != prevB) {
isRemove = false;
}
}
}
if (!isSame && !isChanged && !isAdd && !isRemove) {
return false;
}
}
if (isSame) {
if (a.hasNext()) {
a.next();
return !a.hasNext();
} else if (b.hasNext()) {
b.next();
return !b.hasNext();
} else {
return true;
}
}
if (isChanged) {
if (!a.hasNext() && !b.hasNext()) {
return true;
}
}
if (isRemove) {
if (a.hasNext()) {
prevA = a.next();
return prevA == curB && !a.hasNext();
}
}
if (isAdd) {
if (b.hasNext()) {
prevB = b.next();
return prevB == curA && !b.hasNext();
}
}
return false;
}

http://www.cnblogs.com/EdwardLiu/p/4245378.html

public class Solution {
 2     class IntFileIterator {
 3         boolean hasNext();
 4         int next();
 5     }
 6     
 7     public boolean isDistanceZeroOrOne(IntFileIterator a, IntFileIterator b) {
 8         return check(a, b, 0);
 9     }
10   
11       public boolean check(IntFileIterator a, IntFileIterator b, int distance){
12           IntFileIterator aa = new InFileIterator(a); // copy of iterator a before next() function
13           IntFileIterator bb = new InFileIterator(b);
14           while (a.hasNext() && b.hasNext()) {
15               int s = a.next();
16               int t = b.next();
17               if(s != t){
18                   IntFileIterator aaa = new InFileIterator(a); //copy of iterator a after next() function
19                   IntFileIterator bbb = new InFileIterator(b);
20                   distance++;
21                   if(distance>1) return false;
22                   return check(aa, b, distance) || check(a, bb, distance) || check(aaa, bbb, distance);
23               }
24               else{
25                   return check(a, b, distance);
26               }
27           }
28           
29           if(distance == 1){
30               return !a.hasNext() && !b.hasNext();
31           }else { //(distance ==0)
32               IntFileIterator k = a.hasNext()? a : b;
33               int count = 0;
34               while (k.hasNext()) {
35                   k.next();
36                   count++; // exit early

                     if(count >1) return false;
37               }
38               return count<=1;
39           }
40       }
41 }

https://moonstonelin.wordpress.com/2015/03/12/isdistancezeroorone/

```
  interface IntIterator {
```
```
    boolean hasNext();
```
```
    int next();
```
```
  }
```
```
 
```

  static boolean isDistanceZeroOrOne(IntIterator a, IntIterator b) {

```
    boolean trying = false;
```
```
    boolean changable = false;
```
```
    boolean insertable = false;
```
```
    boolean removable = false;
```

    for(int aPrevious = 0, bPrevious = 0, aCurrent = 0, bCurrent = 0;

        ; aPrevious = aCurrent, bPrevious = bCurrent) {

```
      if(a.hasNext()) {
```
```
        aCurrent = a.next();
```

        if(b.hasNext()) { // a != null, b != null.

```
          bCurrent = b.next();
```
```
          if(trying) {
```
```
            if(changable) {
```

              if(aCurrent != bCurrent) {

```
                changable = false;
```
```
              }
```
```
            }
```
```
            if(insertable) {
```

              if(bCurrent != aPrevious) {

```
                insertable = false;
```
```
              }
```
```
            }
```
```
            if(removable) {
```

              if(aCurrent != bPrevious) {

```
                removable = false;
```
```
              }
```
```
            }
```

            if(!changable && !insertable && !removable) {

```
              return false;
```
```
            }
```

          } else if(aCurrent != bCurrent) {

            // start trying all the possibilities.

```
            trying = true;
```
```
            changable = true;
```
```
            insertable = true;
```
```
            removable = true;
```
```
          }
```

        } else { // a != null, b == null.

```
          if(trying) {
```

            if(removable && aCurrent == bPrevious) {

```
              return !a.hasNext();
```
```
            } else {
```
```
              return false;
```
```
            }
```
```
          } else { // remove a.
```
```
            return !a.hasNext();
```
```
          }
```
```
        }
```
```
      } else {
```

        if(b.hasNext()) { // a == null, b != null.

```
          bCurrent = b.next();
```
```
          if(trying) {
```

            if(insertable && bCurrent == aPrevious) {

```
              return !b.hasNext();
```
```
            } else {
```
```
              return false;
```
```
            }
```
```
          } else { // insert b.
```
```
            return !b.hasNext();
```
```
          }
```

        } else { // a == null, b == null.

          // can only fulfill changable if we are trying.

          return trying ? (changable ? true : false) : true;

```
        }
```
```
      }
```
```
    }
```
```
  }
```
```
 
```

  static IntIterator from(final int[] ints) {

```
    return new IntIterator() {
```
```
 
```
```
      int i = 0;
```
```
 
```
```
      @Override
```
```
      public boolean hasNext() {
```
```
        return i < ints.length;
```
```
      }
```
```
 
```
```
      @Override
```
```
      public int next() {
```
```
        return ints[i++];
```
```
      }
```
```
    };
```
```
  }
```

public bool isDistanceZeroOrOne(ref int cnt, IntFileIterator A, IntFileIterator B)

{

    while (A.hasNext() && B.hasNext())

{

        IntFileIterator copyA = A;

        IntFileIterator copyB = B;

        int a = A.next();

        int b = B.next();

        if (a == b)

{

            continue;

}

        else

{

            cnt++;

            if(cnt >= 2)

{

                return false;

}

            return isDistanceZeroOrOne(ref cnt, copyA, B) || 

                   isDistanceZeroOrOne(ref cnt, A, copyB) || 

                   isDistanceZeroOrOne(ref cnt, copyA, copyB);

}

}

    while(A.hasNext())

{

        cnt++;

}

    while(B.hasNext())

{

        cnt++;

}

    return cnt >= 2 ? true : false;

}

https://discuss.leetcode.com/topic/25774/c-solution-for-stream-file-where-you-don-t-know-the-length-of-the-strings

f 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()

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 isDistanceZeroOrOne | Moonstone

Facebook isDistanceZeroOrOne | Moonstone

Labels

Popular Posts