如何有效地檢查兩個字符串之間的Levenshtein編輯距離是否爲1

Question

請注意，它並不需要真正計算Levenshtein編輯距離。只是檢查它是否1。

該方法的簽名可以是這樣的：

bool Is1EditDistance(string s1, string s2). 

例如： 1. 「ABC」 和 「AB」 返回真 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。
• 如果字符串長度有和nn+1，讓i是哪裏s1[i] != s2[i]，然後循環j=i..n所有j檢查s1[j] == s2[j+1]最小的指數。