class Solution:
    def editDistance(self , str1: str, str2: str) -> int:
        n1 = len(str1)
        n2 = len(str2)

        dp = [[0 for _ in range(n1+1)] for _ in range(n2+1)]

        for i in range(1, n1+1):
            dp[0][i] = dp[0][i-1] + 1

        for i in range(1, n2+1):
            dp[i][0] = dp[i-1][0] + 1

        for i in range(1, n2+1):
            for j in range(1, n1+1):
                if str1[j-1] == str2[i-1]:
                    dp[i][j] = dp[i-1][j-1]
                else:
                    dp[i][j] = min(dp[i-1][j-1], min(dp[i-1][j], dp[i][j-1])) + 1
        
        return dp[-1][-1]

解题思路

• 先构建一个空矩阵，之后给第一行和第一列分别附上索引值+1；
• 遍历这个矩阵，当前索引值为 i，j，如果str1[j-1]和str2[i-1]相等，则当前的矩阵值等于其左上角的矩阵值；否则，取左上、左、上中的最小值，再加上1，表示需要做一个操作。

复杂度

• 时间复杂度和空间复杂度都是O（mn）。