C++로 확인하는 한 번의 편집 거리(Edit Distance) 문제 풀이

두 개의 문자열 s와 t가 주어졌을 때, 두 문자열이 한 번의 편집 거리(One Edit Distance)만큼 차이가 나는지 판별하는 문제를 살펴보겠습니다.

편집 거리의 세 가지 유형

• 문자열 s에 문자 하나를 삽입하여 t를 만든다
• 문자열 s에서 문자 하나를 삭제하여 t를 만든다
• 문자열 s의 문자 하나를 교체하여 t를 만든다

예를 들어 입력이 s = "ab", t = "acb"라면, s에 'c'를 삽입하면 t가 되므로 출력은 True(참)입니다.

해결 접근 방법

이 문제는 다음 단계를 따라 해결할 수 있습니다.

1. n := s의 길이, m := t의 길이로 설정합니다.
2. 만약 n < m이라면, 인수 순서를 바꾸어 isOneEditDistance(t, s)를 재귀적으로 호출합니다. 즉, 항상 더 긴 문자열이 s가 되도록 정렬합니다.
3. i := 0부터 i < m까지 반복하며 다음을 검사합니다.
   • s[i]와 t[i]가 다르다면:
     • n == m인 경우(길이가 같음 → 교체 상황): s의 i+1 이후 부분과 t의 i+1 이후 부분이 같으면 true를 반환합니다.
     • 그 외의 경우(n = m + 1 → 삽입/삭제 상황): s의 i+1 이후 부분과 t의 i 이후 부분이 같으면 true를 반환합니다.
4. 반복문이 끝날 때까지 모든 문자가 같았다면, m + 1 == n일 때 true를 반환합니다. 이는 s가 t보다 정확히 한 글자 긴 경우에 해당합니다.

C++ 구현 예제

아래 코드를 통해 더 잘 이해해 보겠습니다.

#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"

출력

1

복잡도 분석

이 알고리즘은 최악의 경우 짧은 문자열의 길이 m만큼 순회하므로 시간 복잡도는 O(m), 추가 공간 없이 비교만 수행하므로 공간 복잡도는 O(1)입니다. substr 함수가 새 문자열을 생성하는 것을 고려하면 실제 구현에서는 O(m)의 공간이 사용될 수 있으나, 인덱스 기반 비교로 최적화하면 O(1)로 줄일 수 있습니다.