Levenshtein 편집 거리가 1 문자열인지 확인하는 방법

Question

실제로 편집 거리를 계산할 필요가 없습니다. 그냥 1인지 확인하십시오.

메소드의 서명은 다음과 같이 보일 수 있습니다 :

예를 들어

bool Is1EditDistance(string s1, string s2). 

: 1. "ABC"와 "AB"반환 사실 2. "abc 방송"과 "aebc"true를 반환 3 "abc"및 "a"는 false를 반환합니다.

재귀 적 승인을 시도했지만 효율적이지 않습니다.

---

업데이트 : 거리가 정확히 1인지 아닌지 만 신경 경우

 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

, 당신은 같은 것을 할 수 있습니다 :

• 경우] 친구의 대답을 얻었다 문자열 길이의 차이가 0 또는 1이 아닌 경우 false를 반환합니다.
• 두 문자열의 길이가 모두 n 인 경우 루프 i = 0..ns1[i] == s2[i]을 확인하십시오. 모두 i (하나만 제외)입니다. 문자열의 길이 n 및 n+1이있는 경우
• , i이 s1[i] != s2[i], 다음 루프 j=i..n 모든 j에 대한 s1[j] == s2[j+1]을 확인하는 가장 작은 인덱스가 될 수 있습니다.