[Leetcode/파이썬] 72. Edit Distance

Edit Distance

---

Given two strings word1 and word2, return the minimum number of operations required to convert word1 to word2.

You have the following three operations permitted on a word:

• Insert a character
• Delete a character
• Replace a character

 

Example 1:

Input: word1 = "horse", word2 = "ros"
Output: 3
Explanation: 
horse -> rorse (replace 'h' with 'r')
rorse -> rose (remove 'r')
rose -> ros (remove 'e')

Example 2:

Input: word1 = "intention", word2 = "execution"
Output: 5
Explanation: 
intention -> inention (remove 't')
inention -> enention (replace 'i' with 'e')
enention -> exention (replace 'n' with 'x')
exention -> exection (replace 'n' with 'c')
exection -> execution (insert 'u')

 

Constraints:

• 0 <= word1.length, word2.length <= 500
• word1 and word2 consist of lowercase English letters.

 

class Solution:
    def minDistance(self, word1: str, word2: str) -> int:
        m, n = len(word1), len(word2)
        dp = [[0] * (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(1, m + 1) :
            for j in range(1, n + 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], dp[i][j-1], dp[i-1][j-1]) + 1

        return dp[-1][-1]

동작이 어떻게 되는지는 알겠는데, 이게 왜 이렇게 설계됐는지는 잘 모르겠네. 

• if 부분 이해 안됨.
• else 부분 이해 안됨.

이게 문자를 삽입, 삭제, 교체 밖에 안 되서 이런식으로 설계한 것은 이해가 되나, 머리로는 이해가 잘 되지 않는다.