今日任务：

1. LeetCode583 两个字符串的删除操作
2. LeetCode72 编辑距离

资料来源：

1. 代码随想录 | LeetCode583 两个字符串的删除操作
2. 代码随想录 | LeetCode72 编辑距离

1 LeetCode583 两个字符串的删除操作

输入: word1 = "sea", word2 = "eat"
输出: 2
解释: 第一步将 "sea" 变为 "ea" ，第二步将 "eat "变为 "ea"

输入：word1 = "leetcode", word2 = "etco"
输出：4

先明确dp数组的含义：word1[i - 1]和word2[j - 1]要达成一致所需要的最小操作次数。那么，对于dp[i][j]来说，如果想要求出dp数组的目标，无非就是看情况对相对于word1[i - 2]和word2[j - 2]来说的新增的最后一个字符进行操作，递推关系这就有了：

• 如果word1[i - 1] == word2[j - 1]，那么说明新增的两个字符相同，不需要进行操作，dpArray[i][j]直接等于dpArray[i - 1][j - 1]即可。
• 如果word1[i - 1] != word2[j - 1]，那么说明新增的两个字符不同，需要选择一个字符进行删除，或者选择两个都删。删除一个，步骤+1；删除两个，步骤+2。dpArray[i][j]就等于min(dpArray[i - 1][j] + 1, dpArray[i][j - 1] + 1, dp[i - 1][j - 1] + 2)。但是又因为dp[i - 1][j - 1] + 2其实和前两个同义（两个字符都删除，其实就等于在不考虑一个字符的情况下删除另一个字符，联系dp数组定义就能明白），所以可以直接简化为dpArray[i][j] = min(dpArray[i - 1][j] + 1, dpArray[i][j - 1] + 1)。

另外还要注意初始化，第一排和第一列都要初始化为1，2，3，4……。联系dp数组说明，第一列和第一排要匹配的就是空字符串，那么dpArray[0][0]就是两个字符串互相匹配，那确实不需要任何操作就能相同；对于dpArray[i][0]和dpArray[0][i]来说，就是字符串和空字符串进行匹配，所以得把字符串删成空字符串才能相同，所以操作数即为字符串的长度。

go
func minDistance(word1 string, word2 string) int {
	dpArray := make([][]int, len(word1) + 1)
	for i := range dpArray {
		dpArray[i] = make([]int, len(word2) + 1)
		dpArray[i][0] = i
	}
	
	for i := range dpArray[0] {
		dpArray[0][i] = i
	}
	
	for i := 1; i < len(word1) + 1; i++ {
		for j := 1; j < len(word2) + 1; j++ {
			if word1[i - 1] == word2[j - 1] {
				dpArray[i][j] = dpArray[i - 1][j - 1]
			} else {
				dpArray[i][j] = min(dpArray[i - 1][j] + 1, dpArray[i][j - 1] + 1)
			}
		}
	}
	return dpArray[len(word1)][len(word2)]
}

2 LeetCode72 编辑距离

输入：word1 = "horse", word2 = "ros"
输出：3
解释：
horse -> rorse (将 'h' 替换为 'r')
rorse -> rose (删除 'r')
rose -> ros (删除 'e')

输入：word1 = "intention", word2 = "execution"
输出：5
解释：
intention -> inention (删除 't')
inention -> enention (将 'i' 替换为 'e')
enention -> exention (将 'n' 替换为 'x')
exention -> exection (将 'n' 替换为 'c')
exection -> execution (插入 'u')

这一题和上一题其实是差不多的，只是多了一个替换操作和一个插入操作，其他的都没变，所以就直接说递推里替换和插入怎么递推。

• 替换操作：替换操作就是把word1[i]强行替换成word2[j]的操作，那就是相当于在匹配成功的基础上多了一步而已，那递推关系就是dp[i - 1][j - 1] + 1。
• 插入操作：插入操作可以等效认为是删除操作。想一下'a'和'ab'两个字符串，在前者的基础上插入一个b和在后者基础上删除一个b的效果其实是一样的（题目不要求处理结果，只要求相同），所以插入的递推关系和删除的递推关系是一样的。

go
func minDistance(word1 string, word2 string) int {
	dpArray := make([][]int, len(word1) + 1)
	for i := range dpArray {
		dpArray[i] = make([]int, len(word2) + 1)
		dpArray[i][0] = i
	}
	for i := range dpArray[0] {
		dpArray[0][i] = i
	}
	
	for i := 1; i < len(word1) + 1; i++ {
		for j := 1; j < len(word2) + 1; j++ {
			if word1[i - 1] == word2[j - 1] {
				dpArray[i][j] = dpArray[i - 1][j - 1]
			} else {
				dpArray[i][j] = min(dpArray[i - 1][j - 1], min(dpArray[i - 1][j], dpArray[i][j - 1])) + 1
			}
		}
	}
	return dpArray[len(word1)][len(word2)]
}