string - how to efficiently check if the Levenshtein edit distance between two string is 1

Question

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;

Answer 1

如果您只关心距离是否恰好为 1，则可以执行以下操作：

• 如果字符串的长度之差不是 0 或 1，则返回 false。
• 如果两个字符串都有长度n，则循环i = 0..n检查除一个之外s1[i] == s2[i]的所有字符串。i
• 如果字符串有长度n和n+1，让i最小的索引 where s1[i] != s2[i]，然后循环j=i..n检查s1[j] == s2[j+1]所有j。