LeetCode - 72. Edit Distance (python)

https://leetcode.com/problems/edit-distance/description/?envType=study-plan-v2&envId=top-interview-150

• 난이도 : medium
• 알고리즘 : 편집거리 알고리즘

접근방법

• word1 에서 word2 로의 최소 편집거리를 구한다.
• cache[word1_len + 1][word2_len + 1]의 배열을 구성한다.
• cache[i][j] 는 word1[:i+1] 에서 word2[:j+1]으로 바꾸는데의 최소 비용
• 점화식
  • word1[i] == word2[j]일 때
    • cache[i][j] = cache[i - 1][j - 1]
  • 그 외
    • cache[i][j] = min(cache[i - 1][j], cache[i][j - 1], cache[i - 1][j - 1]) + 1

소스코드

class Solution:
    def minDistance(self, word1: str, word2: str) -> int:
        n = len(word1)
        m = len(word2)
        cache = [[0 for _ in range(m + 1)] for _ in range(n + 1)]

        for i in range(n + 1):
            cache[i][0] = i
        for i in range(m + 1):
            cache[0][i] = i

        for i in range(1, n + 1):
            for j in range(1, m + 1):
                if word1[i - 1] == word2[j - 1]:
                    cache[i][j] = cache[i - 1][j - 1]
                else:
                    cache[i][j] = min(cache[i - 1][j], cache[i][j - 1], cache[i - 1][j - 1]) + 1
            
        return cache[n][m]