Python으로 두 문자열의 편집 거리가 정확히 1인지 확인하는 방법

문제 이해하기

두 문자열 s와 t가 주어졌을 때, 두 문자열 사이의 편집 거리(edit distance)가 정확히 1인지 확인해야 합니다. 여기서 편집 거리란 한 문자열을 다른 문자열로 변환하기 위해 필요한 연산 횟수를 의미하며, 허용되는 연산은 다음 세 가지입니다.

문자 삽입(Insert)
문자 삭제(Delete)
문자 교체(Replace)

예를 들어, 입력이 s = "hello", t = "heillo"라면 결과는 True입니다. s에 문자 'i' 하나만 삽입하면 t를 만들 수 있기 때문입니다.

접근 방법

이 문제는 두 포인터를 활용해 선형 시간 안에 해결할 수 있습니다. 핵심 아이디어는 두 문자열을 앞에서부터 동시에 비교하면서, 불일치가 발생했을 때 문자열 길이 관계에 따라 어떤 연산(삽입·삭제·교체)이 적용되었는지 판단하는 것입니다. 알고리즘 단계는 다음과 같습니다.

두 문자열 길이 차이의 절댓값이 1보다 크면 False를 반환합니다. 한 번의 편집으로는 길이를 1 이상 줄이거나 늘릴 수 없기 때문입니다.
편집 횟수 카운터(edit_dist_cnt)와 두 인덱스(i, j)를 0으로 초기화합니다.
i가 s의 길이보다 작고 j가 t의 길이보다 작은 동안 반복합니다.
- s[i]와 t[j]가 다른 경우:
  - 이미 편집 횟수가 1이라면 더 이상 진행할 수 없으므로 False를 반환합니다.
  - s가 더 길면 삭제 연산으로 간주하여 i만 증가시킵니다.
  - t가 더 길면 삽입 연산으로 간주하여 j만 증가시킵니다.
  - 길이가 같으면 교체 연산으로 간주하여 i와 j를 모두 증가시킵니다.
  - 편집 횟수를 1 증가시킵니다.
- 두 문자가 같으면 i와 j를 모두 증가시킵니다.
반복이 끝난 후 어느 한 문자열에 아직 처리하지 못한 문자가 남아 있다면, 그것은 마지막 위치에서의 삽입 또는 삭제에 해당하므로 편집 횟수를 1 증가시킵니다.
편집 횟수가 정확히 1이면 True, 그렇지 않으면 False를 반환합니다.

구현 예제

아래 코드를 통해 위 알고리즘이 실제로 어떻게 동작하는지 확인해 보겠습니다.

def solve(s, t):
    if abs(len(s) - len(t)) > 1:
        return False
    edit_dist_cnt = 0
    i = 0
    j = 0
    while i < len(s) and j < len(t):
        if s[i] != t[j]:
            if edit_dist_cnt == 1:
                return False
            if len(s) > len(t):
                i += 1
            elif len(s) < len(t):
                j += 1
            else:
                i += 1
                j += 1
            edit_dist_cnt += 1
        else:
            i += 1
            j += 1
    if i < len(s) or j < len(t):
        edit_dist_cnt += 1
    return edit_dist_cnt == 1

s = "hello"
t = "heillo"
print(solve(s, t))

실행 결과

입력:

"hello", "heillo"

출력:

True

복잡도 분석

시간 복잡도: O(n + m) — n과 m은 각각 문자열 s와 t의 길이입니다. 두 포인터가 각 문자열을 한 번씩만 순회합니다.
공간 복잡도: O(1) — 추가적인 자료 구조 없이 몇 개의 변수만 사용합니다.