[Algorithm] 편집 거리

출처 - 이코테 p.382 문제

 

편집 거리 알고리즘.. 잘 이해 안 됐는데 거의 80% 정도까지 이해하도록 도와준 영상이 있다.

이분 영상 너무 좋다. 다른 영상도 계속 보면 도움될 것 같음

https://www.youtube.com/watch?v=XJ6e4BQYJ24&t=661s 

 

여기서 감명깊었던게 "Adding a character to A is equivalent to deleting a character from B" 이다.

 

def edit_dist(str1, str2):
    n = len(str1)
    m = len(str2)

    # 2차원 dp 테이블 초기화 (맨 첫번째 행열은 각각 빈 문자열)
    dp = [[0] * (m + 1) for _ in range(n + 1)]

    # dp 테이블 초기 설정
    for i in range(1, n + 1):
        dp[i][0] = i
    for j in range(1, m + 1):
        dp[0][j] = j

    # 최소 편집 거리 계산
    for i in range(1, n + 1):
        for j in range(1, m + 1):
            # 문자가 같다면, 왼쪽 위에 해당하는 수를 그대로 대입
            if str1[i - 1] == str2[j - 1]:
                dp[i][j] = dp[i - 1][j - 1]
            # 문자가 다르다면, 3가지 경우 중에서 최솟값 찾기
            else:
                dp[i][j] = 1 + min(dp[i][j - 1], dp[i - 1][j], dp[i - 1][j - 1])
    return dp[n][m]


# 두 문자열 입력받기
str1 = input()
str2 = input()

# 최소 편집 거리 출력
print(edit_dist(str1, str2))