Accepted clean Java solution with explanation (two pointers)


  • 15

    The basic idea is we keep comparing s and t from the beginning, once there's a difference, we try to replace s(i) with t(j) or insert t(j) to s(i) and see if the rest are the same.

    Example: i and j are the two pointers of S and T, we found that 'b' != 'c' and we try to replace it:

         i                           i
    S: a c d      replace       S: a b d
    T: a b c d   --------->     T: a b c d    --->  "d" != "cd", no good
         j                           j
    

    now we try to insert T(j) to S(i) and we get:

         i                           i
    S: a c d      insert        S: a b c d
    T: a b c d   --------->     T: a b c d    --->  "cd" == "cd", viola!
         j                           j
    

    To keep the code simple, we make s is always shorter than t, so we don't need to try deletion.

    Code:

    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;
    }

  • 0
    C

    Nice solution, I rewrite it in Python language:

    def isOneEditDistance(self, s, t):
        m, n = len(s), len(t)
        if m > n:
            return self.isOneEditDistance(t, s)
        if n-m > 1:
            return False
        i, j = 0, 0
        while i < m and j < n:
            if s[i] != t[j]:
                return s[i+1:] == t[j+1:] or s[i:] == t[j+1:]
            i += 1; j += 1
        return n-m == 1

  • 4
    A

    Excellent idea!
    But 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. I have implemented your idea without using index j, and it was accepted.

    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;
    }

  • 0

    Yeah you are right!


  • 0
    N

    Doesn't the substring() operation in Java 7 and higher consume a O(N) complexity?


  • 0

    Thanks mate!


  • 0
    Y
    This post is deleted!

  • 0
    D
      return t.length() - j == 1;
    

    Could you explain why you have this statement please? Thanks.


  • 0
    M

    @DanielMan97 It is to check if the difference between lengths of both the strings is 1, I believe. After you get out of the for loop, you can imply that all the comparisons were successful. So, in order to get the exact edit distance 1, there has to be one operation performed which is, in this case, would be an append operation.

    As per my understanding, you can also rewrite the last statement to something like:

    return Math.abs(s.length() - t.length()) == 1;
    

    This statement will serve the exact same purpose as the one used in the existing code, in my opinion.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.