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

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param str1 string字符串 
# @param str2 string字符串 
# @return int整型
#
class Solution:
    def editDistance(self , str1: str, str2: str) -> int:
        # write code here
        n, m = len(str1), len(str2)
        f = [[0] * (m + 1) for _ in range(n + 1)]
        f[0] = list(range(m + 1))
        for i, x in enumerate(str1):
            f[i + 1][0] = i + 1
            for j, y in enumerate(str2):
                f[i + 1][j + 1] = f[i][j] if x == y else \
                min(f[i][j + 1], f[i + 1][j], f[i][j]) + 1
        return f[n][m]