[LeetCode] 72. Edit Distance

김민우·2023년 2월 26일

leetcode

알고리즘

목록 보기

150/189

- Problem

72. Edit Distance

word1에서 word2로 변환하는 데 필요한 최소한의 연산 횟수를 구하는 문제이다. 허용되는 연산으로는 다음과 같다.

삽입 (insert)
삭제 (delete)
교체 (replace)

~~simple but disgusting~~

문제랑 한 시간 정도 눈싸움하다가 최장 공통 부분 문자열(LCS, Longest Common Subsequence)과 비슷한 접근법으로 해결할 수 있다는 느낌을 받았다. 그러나 핵심적인 차이로는 해당 문제는 교체(replace) 연산이 이루어진다는 점이다.

결국엔 해당 영상의 도움을 얻었다.

영상보다 설명을 잘 할 자신이 없으니 혹시나 풀이가 필요하다면 영상을 봐주세요.🙏

레벤슈타인 거리(Levenshtein distance) 혹은 편집 거리 알고리즘 라고도 불리우는 알고리즘을 이용하여 해결해야 한다.
레벤슈타인 거리는 단어를 다른 단어로 변경하는 데 필요한 최소한의 편집 수를 말한다.

- 내 풀이 1 (DP, Memoization)

class Solution:
    def minDistance(self, word1: str, word2: str) -> int:
        @lru_cache
        def memoization(i: int, j: int) -> int:
            if not i or not j:
                return i or j
            
            if word1[i-1] == word2[j-1]:
                return memoization(i-1, j-1)
            
            else:
                return 1 + min(memoization(i-1, j), memoization(i, j-1), memoization(i-1, j-1))
        
        return memoization(len(word1), len(word2))

top-down 방식의 접근으로, 마지막 문자부터 시작하여 편집 거리를 찾는 방법이다. functools의 @lru_cache를 이용하여 함수의 결과 값을 캐싱하여 문제를 해결한다.
아래에 작성할 bottom-up 방식보다 직관적이지만 주어진 word1, word2의 길이가 길어진다면 stack overflow 위험이 있다.

- 내 풀이 2 (DP, Tabulation)

class Solution:
    def minDistance(self, word1: str, word2: str) -> int:
        M, N = len(word1), len(word2)

        dp = [[0 for _ in range(N+1)] for _ in range(M+1)]

        for i in range(M+1):
            dp[i][0] = i

        for j in range(N+1):
            dp[0][j] = j
        
        for i in range(M):
            for j in range(N):
                if word1[i] == word2[j]:
                    dp[i+1][j+1] = dp[i][j]
                else:
                    dp[i+1][j+1] = 1 + min(dp[i+1][j], dp[i][j+1], dp[i][j])
        
        return dp[-1][-1]