Sunday, November 16, 2014

Facebook: One edit distance

Check if two given strings differ at most one edit distance.

public class Solutoin {
    public boolean isOneEditDistance(String s1, String s2) {
        if (s1.length() == 0 && s2.length() == 0) {
            return true;
        }
        
        if (Math.abs(s1.length() - s2.length()) > 1) {
            return false;
        }
        
        int count = 0;
        int len1= s1.length();
        int len2 = s2.length();
        
        for (int i = 0, j = 0; i < len1 && j < len2; i++, j++) {
            if (s1.charAt(i) != s2.charAt(j)) {
                count++;
                if (count > 1) {
                    return false;
                }
                
                if (len1 > len2) {
                    j--;
                } else if (len1 < len2) {
                    i--;
                }
            }
        }
        
        return count <= 1;
    }
}

Update on 11/30/14:
public class Solution {
    public boolean oneEditDistance(String word1, String word2) {
        if ((word1 == null || word1.length() == 0) && (word2 == null || word2.length() == 0)) {
            return true;
        }
        
        int len1 = word1.length();
        int len2 = word2.length();
        
        int i = 0;
        int j = 0;
        int count = 0;
        
        while (i < len1 && j < len2) {
            if (word1.charAt(i) != word2.charAt(j)) {
                count++;
                if (count > 1) {
                    return false;
                }
                
                if (len1 > len2) {
                    i++; // delete one
                } else if (len1 < len2) {
                    j++; // add one
                } else {
                    i++;
                    j++;    // replace one
                }
            } else {
                i++;
                j++;
            }
        }
        return count < 2;
    }

    public static void main(String[] args) {
        Solution sol = new Solution();
        String word1 = "abcd";
        String word2 = "abed";

        System.out.println(sol.oneEditDistance(word1, word2));
    }

}

No comments:

Post a Comment