[LeetCode] 72. Edit Distance

문제

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

접근

• 2차원 DP로 접근
  • DP 테이블 정의: dp[i][j]를 문자열 word1의 처음 i 글자와 문자열 word2의 처음 j 글자 사이의 Minimum Edit Distance 정의한다. 0~i번째까지의 문자열에서, 0~j번째까지의 문자열로 수정하는 데 드는 최소 횟수
  • 초기값 설정: 빈 문자열에서 다른 문자열로 변환하는 데 필요한 편집 거리는 문자열의 길이와 같다. 즉, dp[i][0] = i (i 글자 삭제)와 dp[0][j] = j (j 글자 삽입)로 설정한다
  • DP 테이블 채우기
    • 만약 word1[i-1]와 word2[j-1]가 같다면, dp[i][j] == dp[i-1][j-1] 왜냐하면 어차피 뒷 부분은 같기 때문에 앞 부분을 바꾸는데 필요한 명령만 실행하면 되기 때문이다.
    • 만약 다르다면, 다음 세 가지 조작 중 최소 비용을 고려해 dp[i][j]를 결정해야 한다.
      삽입: dp[i][j-1] + 1 (word2[j-1]를 삽입)
      삭제: dp[i-1][j] + 1 (word1[i-1]를 삭제)
      교체: dp[i-1][j-1] + 1 (word1[i-1]를 word2[j-1]로 교체)

Code

class Solution:
    def minDistance(self, word1: str, word2: str) -> int:
        dp = [[0 for _ in range(len(word2)+1)] for _ in range (len(word1)+1)]
        dp[0][0] = 0
        
        for i in range(1, len(word1)+1):
            dp[i][0] = i
            
        for i in range(1, len(word2)+1):
            dp[0][i] = i
            
        for i in range(1, len(word1)+1):
            for j in range(1, len(word2)+1):
                if word1[i-1] == word2[j-1]: 
                    dp[i][j] = dp[i-1][j-1]
                else: 
                    dp[i][j] = min(dp[i-1][j-1] + 1, dp[i-1][j] + 1, dp[i][j-1] + 1)
        return dp[len(word1)][len(word2)]

참고: 편집거리 알고리즘