Python으로 두 문자열의 편집 거리가 0 또는 1인지 확인하는 프로그램

두 개의 문자열 S와 T가 주어졌을 때, 이 두 문자열이 편집 거리(edit distance) 0 또는 1 이내인지 확인하는 문제를 살펴보겠습니다.

여기서 말하는 편집 연산은 다음 세 가지 중 하나를 의미합니다.

문자 하나 삭제하기
문자 하나 추가하기
기존 문자를 다른 문자로 교체하기

예시로 이해하기

예를 들어 입력이 S = "hello", T = "hallo"라고 가정해 보겠습니다. 'e'를 'a'로 한 번만 교체하면 되므로 편집 거리는 1이고, 따라서 출력은 True가 됩니다.

반면 두 문자열의 길이 차이가 2 이상이라면, 어떤 편집 연산을 아무리 사용해도 거리를 1 이하로 만들 수 없으므로 즉시 False를 반환할 수 있습니다.

해결 접근 방법

이 문제는 투 포인터(two pointer) 기법을 활용해 선형 시간에 해결할 수 있습니다. 알고리즘의 동작 순서는 다음과 같습니다.

m := S의 길이, n := T의 길이로 초기화합니다.
포인터 i := 0, j := 0, 그리고 불일치 횟수 count := 0으로 설정합니다.
|m − n| > 1이면 False를 반환합니다.
i < m이고 j < n인 동안 반복합니다.
- S[i]와 T[j]가 다르면:
  - count가 이미 1이면 False를 반환합니다.
  - m < n이면 j를 1 증가시킵니다 (T에서 문자가 삽입된 경우).
  - m > n이면 i를 1 증가시킵니다 (S에서 문자가 삭제된 경우).
  - 그 외의 경우(길이가 같으면 교체)에는 i와 j를 모두 1씩 증가시킵니다.
  - count를 1 증가시킵니다.
- S[i]와 T[j]가 같으면 i와 j를 모두 1씩 증가시킵니다.
반복이 끝나면 True를 반환합니다.

Python 구현 코드

class Solution:
    def solve(self, S, T):
        m, n = len(S), len(T)
        i, j = 0, 0
        count = 0
        if abs(m - n) > 1:
            return False
        while i < m and j < n:
            if S[i] != T[j]:
                if count == 1:
                    return False
                if m < n:
                    j += 1
                elif m > n:
                    i += 1
                else:
                    i += 1
                    j += 1
                count += 1
            else:
                i += 1
                j += 1
        return True

ob = Solution()
S = "hello"
T = "hallo"
print(ob.solve(S, T))

입력

"hello", "hallo"

출력

True

복잡도 분석

시간 복잡도: O(m + n) — 두 문자열을 각각 한 번씩만 순회하면 됩니다.
공간 복잡도: O(1) — 추가적인 자료구조 없이 포인터와 카운터만 사용합니다.

이처럼 길이 차이를 먼저 검사하고, 불일치가 발생했을 때 어느 쪽 포인터를 앞으로 이동할지 판단하는 방식으로, 전체 편집 거리 계산 없이도 두 문자열이 최대 1번의 편집으로 같아질 수 있는지 효율적으로 확인할 수 있습니다.