Leetcode: One Edit Distance

╰+哭是因爲堅強的太久メ 2021-10-23 07:15 195阅读 0赞

Given two strings S and T, determine if they are both one edit distance apart.

注意这道题：Must be exactly one distance apart. Not the same.

1 public class Solution {
     2     public boolean isOneEditDistance(String s, String t) {
     3         for (int i=0; i<Math.min(s.length(), t.length()); i++) {
     4             if (s.charAt(i) != t.charAt(i)) {
     5                 if (s.length() == t.length()) 
     6                     return s.substring(i+1).equals(t.substring(i+1));
     7                 else if (s.length() < t.length()) {
     8                     return s.substring(i).equals(t.substring(i+1));
     9                 }
    10                 else return t.substring(i).equals(s.substring(i+1));
    11             }
    12         }
    13         
    14         //Corner case, last char
    15         return Math.abs(s.length() - t.length()) == 1;
    16     }
    17 }

另外FB面经有一道比较狠的这个题的变形：

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再比），那么一个个往前  
跑的时候就得三种情况都考虑。。。。

我的做法：

1 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++;
    37               }
    38               return k<=1;
    39           }
    40       }
    41 }

转载于:https://www.cnblogs.com/EdwardLiu/p/4245378.html