How to effectively check if Levenshtein’s editing distance between two lines is 1

Question

note that it does not require to really calculate the editing distance of Levenshtein. just check it is 1 or not.

The method signature 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 tried recursively asserting, but that is not efficient.

---

update: received a response 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

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

• If the difference in string lengths is not 0 or 1, return false.
• If both lines are of length n , the cycle i = 0..n checks s1[i] == s2[i] for all i except one.
• If the strings are of length n and n+1 , let i be the smallest index, where s1[i] != s2[i] , then the cycle j=i..n check s1[j] == s2[j+1] for all j .