C++에서 하나의 편집 거리

<시간/>

두 개의 문자열 s와 t가 있다고 가정합니다. 둘 다 하나의 편집 거리만큼 떨어져 있는지 확인해야 합니다. 하나의 편집 거리에는 세 가지 유형이 있습니다 -

t를 얻으려면 s에 문자를 삽입하십시오.
s에서 문자를 삭제하여 t
t를 얻으려면 s의 문자를 바꾸십시오.

따라서 입력이 s ="ab", t ="acb"와 같으면 출력은 True

가 됩니다.

이 문제를 해결하기 위해 다음 단계를 따릅니다. −

n :=s의 크기, m :=t의 크기
n
- 반환 isOneEditDistance(t, s)
initialize i :=0의 경우, i
- s[i]가 t[i]와 같지 않으면 -
  - n이 m과 같으면 -
    - 인덱스 0에서 (i)까지의 s의 부분 문자열이 인덱스 0에서 (i)까지의 t의 부분 문자열과 같을 때 true를 반환
  - 인덱스 0에서 (i)까지의 s의 부분 문자열이 인덱스 0에서 (i - 1)까지의 t의 부분 문자열과 같으면 true를 반환합니다.
m + 1이 n
과 같으면 true를 반환합니다.

예시

더 나은 이해를 위해 다음 구현을 살펴보겠습니다. −

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
   bool isOneEditDistance(string s, string t) {
      int n = s.size();
      int m = t.size();
      if (n < m) {
         return isOneEditDistance(t, s);
      }
      for (int i = 0; i < m; i++) {
         if (s[i] != t[i]) {
            if (n == m) {
               return s.substr(i + 1) == t.substr(i + 1);
            }
            return s.substr(i + 1) == t.substr(i);
         }
      }
      return m + 1 == n;
   }
};
main(){
   Solution ob;
   cout << (ob.isOneEditDistance("ab", "acb"));
}

입력

s = "ab", t = "acb"