如何有效地检查两个字符串之间的Levenshtein编辑距离是否为1

Question

请注意,它不需要真正计算Levenshtein编辑距离.只是检查它是否为1.

方法的签名可能如下所示:

bool Is1EditDistance(string s1, string s2). 

例如:1."abc"和"ab"返回true 2."abc"和"aebc"返回true 3."abc"和"a"返回false.

我试过递归批准,但它效率不高.

---

更新:得到了朋友的回答:

        for (int i = 0; i < s1.Length && i < s2.Length; i++)
        {
            if (s1[i] != s2[i])
            {
                return s1.Substring(i + 1) == s2.Substring(i + 1)   //case of change
                    || s1.Substring(i + 1) == s2.Substring(i)       //case of s1 has extra
                    || s1.Substring(i) == s2.Substring(i + 1);      //case of s2 has extra
            }
        }
        return Math.Abs(s1.Length - s2.Length) == 1;

Answer 1

如果您只关心距离是否为1,您可以这样做:

• 如果字符串长度的差异不是0或1,则返回false.
• 如果两个字符串都有长度n,则循环i = 0..n检查s1[i] == s2[i]所有字符串i除外.
• 如果字符串有长度,n并且n+1让它i成为最小的索引s1[i] != s2[i],那么循环j=i..n检查s1[j] == s2[j+1]所有j.