72.M 编辑距离

Problem: 72. 编辑距离

[TOC]

思路

动态规划。

状态定义： dp[i][j]表示将 word1的前 i个字符转换为 word2的前 j个字符所需的最小操作数。

边界条件： dp[i][0] = i：将 word1的前 i个字符转换为空字符串需要 i次删除操作 dp[0][j] = j：将空字符串转换为 word2的前 j个字符需要 j次插入操作

状态转移方程：

v1 := dp[i-1][j] + 1
v2 := dp[i][j-1] + 1
v3 := dp[i-1][j-1]
if word1[i-1] != word2[j-1] {
    v3 += 1
}
dp[i][j] = min(v1, v2, v3)

Code

func minDistance(word1 string, word2 string) int {
	m := len(word1)
	n := len(word2)
	if m*n == 0 {
		return m + n
	}

	dp := make([][]int, m+1)
	for i := range dp {
		dp[i] = make([]int, n+1)
	}

	for i := 1; i <= m; i++ {
		dp[i][0] = i
	}

	for j := 1; j <= n; j++ {
		dp[0][j] = j
	}

	for i := 1; i <= m; i++ {
		for j := 1; j <= n; j++ {
			v1 := dp[i-1][j] + 1
			v2 := dp[i][j-1] + 1
			v3 := dp[i-1][j-1]
			if word1[i-1] != word2[j-1] {
				v3 += 1
			}

			dp[i][j] = min(v1, v2, v3)
		}
	}

	return dp[m][n]
}

// 注意：必须有等号
func min(a, b, c int) int {
	if a <= b && a <= c {
		return a
	} else if b <= a && b <= c {
		return b
	} else {
		return c
	}
}