如何有效地检查，如果两个字符串之间的莱文斯坦编辑距离是1 [英] how to efficiently check if the Levenshtein edit distance between two string is 1

问题描述

请注意，它并不需要真正计算的Levenshtein编辑距离。只是检查它的1与否。

该方法的签名可能是这样的：

 布尔Is1EditDistance（字符串S1，S2线）。
 

例如： 1.ABC和AB回归真实 2，ABC和aebc返回true 3.ABC和A返回false。

我已经试过递归批准，但它是没有效率。

---

更新：接到一个朋友的回答：

 的for（int i = 0; I＆LT; s1.Length和放大器;＆安培; I＆LT; s2.Length;我++）
        {
            如果（S1 [I]！= S2 [I]）
            {
                返回s1.Substring第（i + 1）== s2.Substring第（i + 1）//情况变化
                    || s1.Substring第（i + 1）== s2.Substring（ⅰ）//壳体s1的具有额外
                    || s1.Substring（ⅰ）== s2.Substring第（i + 1）; //情况下，S2的有多余
            }
        }
        返回Math.Abs​​（s1.Length  -  s2.Length）== 1;
 

解决方案

如果你只关心如果距离正好是1或没有，你可以做这样的事情：

• 如果字符串'长度的差不为0或1，返回false。
• 如果两个字符串的长度是 N ，环 I = 0到n 检查 S1 [I] == S2 [I] 所有我只有一个除外。
• 如果字符串的长度是 N 和 N + 1 ，让我是最小的指数，其中 S1 [I]！= S2 [I] ，然后循环 J = i..n 检查 S1 [J] == S2 [J + 1] 所有Ĵ。

please note that it doesn't require to really calculate Levenshtein edit distance. just check it's 1 or not.

The signature of the method may look like this:

bool Is1EditDistance(string s1, string s2). 

for example: 1. "abc" and "ab" return true 2. "abc" and "aebc" return true 3. "abc" and "a" return false.

I've tried recursive approve, but it it not efficient.

---

update: got answer from a friend:

        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;

解决方案

If you only care if the distance is exactly 1 or not, you can do something like this:

• If the difference of the strings' lengths is not 0 or 1, return false.
• If both strings have length n, loop i = 0..n checking s1[i] == s2[i] for all i except one.
• If the strings have length n and n+1, let i be the smallest index where s1[i] != s2[i], then loop j=i..n checking s1[j] == s2[j+1] for all j.

这篇关于如何有效地检查，如果两个字符串之间的莱文斯坦编辑距离是1的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！