[LeetCode]Edit Distance

https://leetcode.com/problems/edit-distance/

Edit Distance - LeetCode

 

문제 분석

주어진 word1을 word2로 만들기 위해 필요한 Operation의 최소 횟수를 구하는 문제입니다. 글자를 insert, delete, replace하는 3가지의 Operation만 가능합니다.

 

처음 시도한 답안

class Solution:
    def minDistance(self, word1: str, word2: str) -> int:
        # 편집거리 알고리즘
        # 두 문자열이 주어지는 경우 얼마나 유사한지 알아낼 수 있는 알고리즘

        dp = [[0 for _ in range(len(word2)+1)] for _ in range(len(word1)+1)]

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

        for j in range(len(word1)+1):
            dp[j][0] = j

        for i in range(1, len(word1)+1):
            for j in range(1, len(word2)+1):
                # 만약 동일한 글자라면 i-1, j-1 즉 이전 위치의 값을 가져옴
                if word1[i-1] == word2[j-1]:
                    dp[i][j] = dp[i-1][j-1]
                # 다른 글자라면, 수정(i-1, j-1) 삽입(i, j-1) 삭제(i, j-1) 한 값중 최소값 + 1
                else:
                    dp[i][j] = min(dp[i-1][j-1], dp[i-1][j], dp[i][j-1],) + 1

        return dp[-1][-1]

접근 방법

1. 문자의 갯수보다 길이가 1긴 dp 이차원 리스트를 생성합니다.
2. 첫번째 행과 첫번째 열은 숫자를 1씩 증감시키면서 초기화합니다.
3. 이차원 그리드를 순회합니다.
   1. 만약 등장한 문자가 서로 같다면 바로 이전 위치인, (i-1, j-1)의 값을 가져옵니다.
   2. 문자가 다르다면 operation이 필요합니다.
      1. 수정(i-1, j-1), 삽입(i, j-1), 삭제(i, j-1)에서 최솟값을 고르고 거기에 연산했다는 +1을 증감합니다.
4. 이중 순회를 마무리하면 가장 마지막 요소에 최소 operation 횟수가 담기게 됩니다.

DP 예시를 보면서 설명을 추가하겠습니다. word1 = horse, word2 = ros로 가정합니다.

	0, O	1, r	2, o	3, s
0, O	0	1	2	3
1, h	1	1	2	3
2, o	2	2	1	2
3, r	3	2	2	2
4, s	4	3	3	2
5, e	5	4	4	3

 

이중 순회를 하면서 등장한 문자가 서로 같다면 대각선 왼쪽 위인 (i-1, j-1) 지점의 값을 가져옵니다. 추가 연산을 수행할 필요가 없기 때문입니다.

등장한 문자가 서로 다르다면 (i-1, j-1) 지점에서 수정 연산을 수행하거나, (i, j-1) 지점에서 삽입 연산을 수행하거나, (i-1, j) 지점에서 삭제 연산을 수행합니다. 가장 최소값을 고르기 위해서 3개의 선택지중 적은 값을 고르고 연산하여 +1을 증감한 값을 저장하도록 합니다.

 

이 문제는 편집 거리 알고리즘 종류에서 리벤슈타인 거리와 동일합니다. 리벤 슈타인 알고리즘은 삽입, 삭제, 대체 연산이 있는 알고리즘입니다. 또 다른 편집 거리 알고리즘의 종류로는 이전에 풀이한 LCS 알고리즘이 존재합니다.

 

이전에 풀이한 LCS 알고리즘 문제

https://leffept.tistory.com/525