给定两个字符串,找出它们是否相互远离一个编辑

Question

我最近遇到了这个问题:

Given two strings, return true if they are one edit away from each other,else return false.
An edit is insert/replace/delete a character. 
Ex. {"abc","ab"}->true, {"abc","adc"}->true, {"abc","cab"}->false

解决此问题的一种方法是使用动态编程找到两个字符串之间的编辑距离,并检查它是否为1.这将花费O(N2)时间.有没有办法在线性时间内完成此操作,因为我们只检查它们是否为1编辑？

我在下面写的代码适用于大多数情况,但是对于像{"m",""}这样的情况却失败了

public boolean isOneEditDistance(String s1,String s2){
    if(s1==null || s2==null)
        return true;
    if(s1.equals(s2))
        return false;
    if (Math.abs(s1.length() - s2.length()) > 1)
        return false;
    int i = -1;
    int j = -1;
    while (true)
    {
        i++;
        j++;
        if (i == s1.length())
            return true;
        if (s1.charAt(i) == s2.charAt(j))
            continue;
        if (i != j)
            return false;
        if (s1.length() < s2.length())
            i--;
        else
            j--;
    }
}

Answer 1

这是在O(n)中找到一个编辑的解决方案.以下是我在实现中介绍的场景.

1. 两个输入字符串之间的长度差异不应超过1.
2. 当字符串的长度相同时,不同字符的数量不应超过1.
3. 如果长度差为1,则可以在短字符串中插入一个char或从较长的字符串中删除.考虑到这一点,不同char的数量不应超过1.

private static boolean isOneEdit(String first, String second) {
    // if the input string are same
    if (first.equals(second))
        return false;

    int len1 = first.length();
    int len2 = second.length();
    // If the length difference of the stings is more than 1, return false.
    if ((len1 - len2) > 1 || (len2 - len1) > 1  ) {
        return false;
    }
    int i = 0, j = 0;
    int diff = 0;
    while (i<len1 && j<len2) {
        char f = first.charAt(i);
        char s = second.charAt(j);
        if (f != s) {
            diff++;
            if (len1 > len2)
                i++;
            if (len2 > len1)
                j++;
            if (len1 == len2)
                i++; j++;
        }
        else{
            i++; j++;
        }
        if (diff > 1) {
            return false;
        }
    }
    // If the length of the string is not same. ex. "abc" and "abde" are not one edit distance.
    if (diff == 1 && len1 != len2 && (i != len1 || j != len2)) {
        return false;
    }
    return true;
}