写在前面

编辑距离算法被数据科学家广泛应用，是用作机器翻译和语音识别评价标准的基本算法。

Ⅰ、题目

	给你两个单词 word1 和 word2，请你计算出将 word1 转换成 word2 所使用的最少操作数。
	你可以对一个单词进行如下三种操作：
		1. 插入一个字符
		2. 删除一个字符
		3. 替换一个字符

Ⅱ、测试样例

	示例 1：
	输入：word1 = "horse", word2 = "ros"
	输出：3
	解释：
		horse -> rorse (将 'h' 替换为 'r')
		rorse -> rose (删除 'r')
		rose -> ros (删除 'e')
	
	示例 2：
	输入：word1 = "intention", word2 = "execution"
	输出：5
	解释：
		intention -> inention (删除 't')
		inention -> enention (将 'i' 替换为 'e')
		enention -> exention (将 'n' 替换为 'x')
		exention -> exection (将 'n' 替换为 'c')
		exection -> execution (插入 'u')
	 
	提示：
		0 <= word1.length, word2.length <= 500
		word1 和 word2 由小写英文字母组成

Ⅲ、分析

	对于单词A、B相对应则会有6种操作：
		A：插入、删除、替换
		B：插入、删除、替换
		1. A插入与B删除  (A[0...i]和B[0...j - 1]的结果 + 1) --> dp[i][j - 1] + 1
		2. A删除与B插入  (A[0...i - 1]和B[0...j]的结果 + 1) --> dp[i - 1][j] + 1
		3. A替换与B替换  (A[0...i - 1]和B[0...j - 1]的结果 + 1) --> dp[i - 1][j - 1] + 1
	
	状态转移方程：
		1. A[i] == B[j] --> dp[i][j] = dp[i - 1][j - 1]
		2. A[i] != B[j] --> min(dp[i][j - 1], dp[i - 1]][j], dp[i - 1][j - 1]) + 1
	
	极端情况考虑：如果出现空字符串，那么操作次数为两字符串长度和。
	第一步：初始化一个二维数组，行为单词A的长度+1，列为单词B的长度+1。
	第二部：边界值初始化。
		第一行的值即为单词A长度为0时，所需的操作次数，即为单词B的长度。
		第一列的值即为单词B长度为0时，所需的操作次数，即为单词A的长度。
	第三步：计算二维数组剩余值。根据上述分析有：
		如果单词A字符与单词B字符相同，那么不需进行任何操作
		否则：
			1. 执行插入操作，那么比较A[0...i]和B[0...j - 1]的结果
			2. 执行删除操作，那么比较A[0...i - 1]和B[0...j]的结果
			3. 执行替换操作，那么比较A[0...i - 1]和B[0...j - 1]的结果
			选择上述三个选项中最小的结果 + 1
			

Ⅳ、代码实现

class Solution:
    def minDistance(self, word1: str, word2: str) -> int:
        len_word1, len_word2 = len(word1), len(word2)
        if len_word1 * len_word2 == 0:
            return len_word1 + len_word2
        # 初始化
        dp = [[0] * (len_word2 + 1) for _ in range(len_word1 + 1)]
        # 边界值初始化
        for i in range(1, len_word1 + 1):
            dp[i][0] = i
        for j in range(1, len_word2 + 1):
            dp[0][j] = j
        # 计算剩余dp
        for i in range(1, len_word1 + 1):
            for j in range(1, len_word2 + 1):
                if word1[i - 1] == word2[j - 1]:
                    dp[i][j] = dp[i - 1][j - 1]
                else:
                    dp[i][j] = min(dp[i][j - 1], dp[i - 1][j], dp[i - 1][j - 1]) + 1

        return dp[len_word1][len_word2]


if __name__ == '__main__':
    sol = Solution()
    print(sol.minDistance(word1='intention', word2='execution'))

Ⅴ、结语

Over！大功告成！
至此，本文到此结束！

关于 动态规划算法：编辑距离 已全部完成。
本文只做学习用途，无任何商业用途！
转载注明出处！祝各位学业有成！
大大怪爱小乖乖！
研哥哥