Tuesday, August 25, 2015

Leetcode: One Edit Distance

http://buttercola.blogspot.com/2014/11/facebook-one-edit-distance.html

Given two strings S and T, determine if they are both one edit distance apart.
Understand the problem:
Note that the problem asks for EXACTLY one edit distance. There are several cases to consider:
  -- If the len1 - len2 > 1, return false; 
  -- We compare each character of the two strings. if not equal. 
   -- If len1 > len2, we move i++, which means delete one character from string1, e.g. abc, ac
   -- If len1 < len2, we move j++, which add one character for string1 (or delete one from string 2).
  --  If len1 == len2, i++, j++

Code (Java):
public class Solution {
    public boolean isOneEditDistance(String s, String t) {
        if ((s == null || s.length() == 0) && (t == null || t.length() == 0)) {
            return false;
        }
        
        if (s == null || s.length() == 0) {
            return t.length() == 1;
        }
        
        if (t == null || t.length() == 0) {
            return s.length() == 1;
        }
        
        if (Math.abs(s.length() - t.length()) > 1) {
            return false;
        }
        
        
        int count = 0;
        int i = 0;
        int j = 0;
        
        while (i < s.length() && j < t.length()) {
            if (s.charAt(i) != t.charAt(j)) {
                count++;
                if (count > 1) {
                    return false;
                }
                
                if (s.length() > t.length()) {
                    i++;
                } else if (s.length() < t.length()) {
                    j++;
                } else {
                    i++;
                    j++;
                }
            } else {
                i++;
                j++;
            }
        }
        
        if (i < s.length() || j < t.length()) {
            count++;
        }
        
        return count == 1;
    }
}

Summary:
The problem itself is not hard, but very tricky to get the OJ passed. Some tricks need to be very very careful:
1. If the length of the two words diff more than 1, directly return false;
2. At the end, we need to check if i < s.length() OR j < t.length(). That is because the problem asks for EXACTLY ONE edit distance. e.g. s = abc, t = ab, in this case. the count = 0. So we need to accumulate the count by 1 in that case. If the problem asks for edit distance which is LESS or EQUAL to 1, then we don't need to check that step.  

No comments:

Post a Comment