题解 | #编辑距离(一)#

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param str1 string字符串 
# @param str2 string字符串 
# @return int整型
#
class Solution:
    def editDistance(self , str1: str, str2: str) -> int:
        n , m = len(str1) , len(str2)
        dp = [[0]*(n) for _ in range(m)]
		#初始化
        if str1[0] != str2[0]:
            dp[0][0] = 1 
        for i in range(1,m):
            dp[i][0] = dp[i-1][0] + 1
        for i in range(1,n):
            dp[0][i] = dp[0][i-1] + 1
		#动态规划计算
        for i in range(1,m):
            for j in range(1,n):
                if str1[j] == str2[i]:
                    dp[i][j] = dp[i-1][j-1]
                else:
                    dp[i][j] = min(dp[i-1][j-1],dp[i-1][j],dp[i][j-1])+1
        return dp[m-1][n-1]