72.编辑距离

给定两个单词 word1 和 word2,计算出将 word1 转换成 word2 所使用的最少操作数 。你可以对一个单词进行如下三种操作:插入一个字符、删除一个字符、替换一个字符
思路:动态规划,如果把单词变短会让这个问题变简单,用D[m][n] 表示输入单词长度为m和n的编辑距离
如果两个子串的最后一个字母相同,
【72.编辑距离】否则,考虑替换最后一个使他们相同,

class Solution: def minDistance(self, word1, word2): """ :type word1: str :type word2: str :rtype: int """ n = len(word1) m = len(word2)# if one of the strings is empty if n * m == 0: return n + m# array to store the convertion history d = [ [0] * (m + 1) for _ in range(n + 1)]# init boundaries for i in range(n + 1): d[i][0] = i for j in range(m + 1): d[0][j] = j# DP compute for i in range(1, n + 1): for j in range(1, m + 1): left = d[i - 1][j] + 1 down = d[i][j - 1] + 1 left_down = d[i - 1][j - 1] if word1[i - 1] != word2[j - 1]: left_down += 1 d[i][j] = min(left, down, left_down)return d[n][m]

    推荐阅读